در مغازه های جریان عدم انتظار و عدم بیکاری با معیار زمان کل On no-wait and no-idle flow shops with makespan criterion
- نوع فایل : کتاب
- زبان : فارسی
- ناشر : الزویر Elsevier
- چاپ و سال / کشور: 2007
توضیحات
چاپ شده در مجله اروپایی تحقیقات عملیاتی – European Journal of Operational Research
رشته های مرتبط ریاضی، آنالیز عددی و محاسبات نرم
۴- ملاحظات نهایی روش مورد استفاده برای مدل سازی زمان کل در زمان بندی عدم انتظار و عدم بیکاری را می توان برای مغازه های ترکیبی پیاده سازی کرد. به این ترتیب مسئله Fmjblock(1,2),no-waitjCmax را در نظر بگیرید به طوری که ذخیره ای بین M1و M2 وجود نداشته باشد و از این روی شرایط عدم انتظار بایستی توسط ماشین های دیگر در نظر گرفته شوند. وقتی که قوس هابا اوزان منفی -p2j از شکل ۱ الف حذف شود، طول مسیر بحرانی در شبکه حاصله، کل زمان متناظر است. به ویژه این نشان می دهد که هر دو F3jblock(1,2),nowait(2,3)jCmax and F3jno-wait(1,2),block(2,3)jCmax به F3jblockjCmax کاهش می یابد. از این روی آن ها ان پی هارد هستند و از این روی می توان به قضایای ۲ و ۳ در ۹ مراجعه کرد. کران پایین L فراتر از ایده اکتشاف سازنده برای حل Fmjprmu,no-idlejCmax(11) می باشد که عملکرد بهتری از اکتشاف های قبلی دارد. ما بر این باوریم که توالی های πhi را می توان برای توسعه یک اکتشاف سازنده Fmjno-waitjCmax مورد استفاده قرار داد که حل آن یک دنباله اولیه برای فرا اکتشافی هاست. ما بر این باوریم که کران پایین L وLhi کاربرد هایی در توسعه الگوریتم های کران و شاخه موثر دارند. ما روابط دو گانه ای را شناسایی کردیم که بین Fmjno-waitjCmax وFmjprmu,no-idlejCmax و FmjblockjCmax وFmjprmu,busyjCmax وجود دارند. تحقیقات آینده برای کشف و بررسی بهتر دوگانگی ها لازم است. امید واریم که مسئله نظری جدید Fmjprmu,busyjCmax زمان بندی مغازه کار هایواقعی معتبر باشند.
رشته های مرتبط ریاضی، آنالیز عددی و محاسبات نرم
۴- ملاحظات نهایی روش مورد استفاده برای مدل سازی زمان کل در زمان بندی عدم انتظار و عدم بیکاری را می توان برای مغازه های ترکیبی پیاده سازی کرد. به این ترتیب مسئله Fmjblock(1,2),no-waitjCmax را در نظر بگیرید به طوری که ذخیره ای بین M1و M2 وجود نداشته باشد و از این روی شرایط عدم انتظار بایستی توسط ماشین های دیگر در نظر گرفته شوند. وقتی که قوس هابا اوزان منفی -p2j از شکل ۱ الف حذف شود، طول مسیر بحرانی در شبکه حاصله، کل زمان متناظر است. به ویژه این نشان می دهد که هر دو F3jblock(1,2),nowait(2,3)jCmax and F3jno-wait(1,2),block(2,3)jCmax به F3jblockjCmax کاهش می یابد. از این روی آن ها ان پی هارد هستند و از این روی می توان به قضایای ۲ و ۳ در ۹ مراجعه کرد. کران پایین L فراتر از ایده اکتشاف سازنده برای حل Fmjprmu,no-idlejCmax(11) می باشد که عملکرد بهتری از اکتشاف های قبلی دارد. ما بر این باوریم که توالی های πhi را می توان برای توسعه یک اکتشاف سازنده Fmjno-waitjCmax مورد استفاده قرار داد که حل آن یک دنباله اولیه برای فرا اکتشافی هاست. ما بر این باوریم که کران پایین L وLhi کاربرد هایی در توسعه الگوریتم های کران و شاخه موثر دارند. ما روابط دو گانه ای را شناسایی کردیم که بین Fmjno-waitjCmax وFmjprmu,no-idlejCmax و FmjblockjCmax وFmjprmu,busyjCmax وجود دارند. تحقیقات آینده برای کشف و بررسی بهتر دوگانگی ها لازم است. امید واریم که مسئله نظری جدید Fmjprmu,busyjCmax زمان بندی مغازه کار هایواقعی معتبر باشند.
Description
۴٫ Final remarks The technique we adapted to model the makespans in no-wait and no-idle flow shops can also be implemented for some hybrid flow shops. To illustrate, consider the problem Fmjblock(1, 2), no-waitjCmax, that is, there is no storage between M1 and M2, and the no-wait condition must be respected by the remaining machines. When the arcs with negative weights p2j are deleted from Fig. 1a, the critical path length in the resulting network is the corresponding makespan. In particular, this shows that both F3jblock(1, 2), nowait(2, 3)jCmax and F3jno-wait(1, 2), block(2, 3)jCmax reduce to F3jblockjCmax, and hence they are strongly NP-hard; see Lemmas 2 and 3 in [9]. The lower bound L falls beyond the idea of a constructive heuristic for solving Fmjprmu, no-idlejCmax [11] that was shown to outperform significantly earlier heuristics. We strongly believe that the sequences phi (in particular p1m) can be used to develop an efficient Fmjno-waitjCmax constructive heuristic whose solution will become a good initial sequence for metaheuristics; see e.g. [4,8]. We also believe that the lower bounds L and Lhi will find applications in developing effective branch and bound algorithms. We identified duality relations that exist between Fmjno-waitjCmax and Fmjprmu, no-idlejCmax, and FmjblockjCmax and Fmjprmu,busyjCmax. Future research is necessary to better explore the observed dualities. We hope that the new theoretical problem Fmjprmu,busyjCmax will find validations in real world flow shop scheduling.
