مدل سازی مساله زمانبندی تولید جریان کارگاهی چند حالته با منابع محدود

نوع مقاله: مقاله پژوهشی

نویسندگان

1 استادیار، گروه مهندسی صنایع، دانشکده مهندسی صنایع و مکانیک، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران

2 دانشیار، گروه مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه خوارزمی، تهران، ایران

چکیده

در مسائل زمانبندی معمولا زمان پردازش عملیات های هر کار مشخص و ثابت در نظر گرفته می شود. در
ادبیات زمانبندی پروژه بسیار تاکید شده است که زمان هر فعالیت/عملیات می تواند گاهی چند حالته باشد و با
تخصیص مقداری بیشتری از منابع به یک فعالیت، زمان پردازش آن نیز کاهش یابد. در اینگونه مسائل علاوه بر
زمانبندی فعالیت ها باید تخصیص منابع محدود در دسترس به فعالیت ها نیز انجام شود. این ضعف در ادبیات
مسائل زمانبندی وجود دارد که زمان پردازش فعالیت ها ثابت فرض می شود. در این مقاله، مسئله جریان
کارگاهی از حالت کلاسیک خود به مسئله جریان کارگاهی چند حالته با منابع محدود توسعه داده می شود. این
مقاله به طور جامع در مورد مدلسازی ریاضی مسئله بحث می کند. در این راستا دو مدل ریاضی به فرم
برنامه ریزی ریاضی عدد صحیح مختلط خطی با دو مفهوم مختلف ارائه می شود. مدل اول، مکان محور و مدل
دوم توالی محور است. برای ارزیابی عملکرد این دو مدل، پیچیدگی اندازه و پیچیدگی محاسباتی آنها تعیین و
مقایسه می شود. در شاخص پیچیدگی اندازه، مدل اول تعداد متغیرهای بیشتر اما تعداد محدودیت های کمتری
در مقایسه با مدل دوم نیاز دارد. در شاخص پیچیدگی محاسباتی، مدل اول عملکرد کاملا بهتری از مدل دوم
ارائه می کند. همچنین مدل اول علاوه بر حل تعداد بیشتری از مسائل به صورت بهینه، زمان کمتری نیز برای
حل در مقایسه با مدل دوم احتیاج دارد

کلیدواژه‌ها


عنوان مقاله [English]

Modelling Multi-Mode Resource-Costrainted Flow Shop Scheduling Problem

نویسندگان [English]

  • Mehdi Yazdani 1
  • Bahman Naderi 2
چکیده [English]

In the scheduling problems, it is commonly assumed that processing times are fixed and known. In the literature of project scheduling emphasizes that the time of each activity/operation can be multi-mode and by assigning more resources, the activity time can be reduced. In these problems, in addition to activity scheduling, allocation of available limited resources to the activities should also be carried out. This assumption that processing time of activities is fixed is a weakness in scheduling literature. This paper develops the classic problem flow shop scheduling to multi-mode resource-cosntrainted flow shop scheduling problem. This paper discusses comprehensively about mathematical modeling. In this regard, two mixed integer linear programming models with two differnet concepts are presented. The first model is location-based model and the second is sequence-based. The performance of the models are evaluated by comparing their size and computational complexities. In the size complexity, the first model requires more variables but less constraints than second Model. In the computational complexity, the first model significantly outperforms than the second Model. Also, the first model, besides solving more problems as optimally, requires less time to solve than the second model

کلیدواژه‌ها [English]

  • Flow Shop Scheduling
  • Multi-Mode
  • Mathematical Modelling
  • Mixed Integer Programming
  • Size And Computational Complexity
Afshar-Nadjafi, B. (2014) A solution procedure for preemptive multi-mode project scheduling problem with mode changeability to resumption, Applied Computing and Informatics, DOI: 10.1016/j.aci.2014.02.003.

Cheng, J., J. Fowler, K. Kempf, S. Mason, (2014) Multi-mode resource-constrained project scheduling problems with non-preemptive activity splitting, Computers and Operations Research, DOI: 10.1016/j.cor.2014.04.018.

Cheng, J., Fowler, J., Kempf, K., (2012) Simulation-based multi-mode resource-constrained project scheduling of semiconductor equipment installation and qualification, Proceedings of the Winter Simulation Conference, 1-12.

Garcia, C., (2016) Resource-constrained scheduling with hard due windows and rejection penalties, Engineering optimization, 48(9), 1515-1528.

Kyriakidis, T.S., G.M. Kopanos, M.C. Georgiadis, (2012) MILP formulations for single- and multi-mode resource-constrained project scheduling problems, Computers and Chemical Engineering, 36, 369–385.

Lee C.H., Liao, C.J., Chung, T.P., (2014) Scheduling with multi-attribute setup times on two identical parallel machines, International Journal of Production Economics, 153, 130-138.

Lin, D., Lee, C.K.M., Ho, W. (2013) Multi-level genetic algorithm for the resource-constrained re-entrant scheduling problem in the flow shop, Engineering Applications of Artificial Intelligence, 26(4), 1282–1290.

Naderi, B., N. Salmasi, (2012) Permutation flowshops in group scheduling with sequence-dependent setup times, European Journal of Industrial Engineering, 6(2), 177-199.

‌Pinedo, M.L. (2008) Theory, algorithms, and systems, 3rd edn. Springer Science+Business Media, New York.

Stafford, E.F., F.T. Tseng, J.N.D. Gupta, (2005) Comparative evaluation of MILP flowshop models, Journal of Operational Research Society, 56, 88–101.

Tseng, F.T., E.F. Stafford, (2008) New MILP models for the permutation flowshop problem, Journal of the Operational Research Society, 59, 1373–1386.

Voß, S., Witt, A., (2007) Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements: A real-world application, International Journal of Production Economics, 105(2), 445–458.

Wang, L., C. Fang, (2011) An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem, Information Sciences, 181(20), 4804-4822.

Yazdani, M., M. Amiri, M. Zandieh, (2010) Flexible job-shop scheduling with parallel variable neighborhood search algorithm, Expert Systems with Applications, 37(1), 678-687.

Zandieh, M., S.M.T. Fatemi Ghomi, S.M. Moattar Husseini, (2006) An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times, Applied Mathematics and Computation, 180(1), 111-127.