زمانبندی جریان کاری ترکیبی با وجود کارهای بدون انتظار: مدل ریاضی و الگوریتم حل

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

نویسنده

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

چکیده

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

کلیدواژه‌ها


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

No-wait hybrid flowshop scheduling: models and solotion algorithms

نویسنده [English]

  • Bahman Naderi
چکیده [English]

In this paper hybrid flowshop scheduling problem where some jobs, not all, have to follow no-wait restriction (that is, the operations of that job must be processed with no stop) is examined. In the literature, all papers assume that all jobs of the shops have to follow no-wait restrictions. First, this paper mathematically formulates the problem with two different mixed integer linear models under proposed considerations. The models are evaluated using two performance measures of size complexity and computational complexity. The small instances of the problem are solved using commercial software of mathematical programming. To solve larger instances of problem, two solution algorithms have been developed. These two algorithms are based on imperialist competitive algorithm and simulated annealing. A comprehensive numerical experiment including small and large instances is conducted to evaluate the models and algorithms. The results show that the imperialist competitive algorithm outperforms simulated annealing

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

  • Hybrid flow shop
  • No-wait scheduling problem
  • mixed integer mathematical programming
  • Simulated Annealing
  • imperialist competitive algorithm
Aldowaisan, T., Allahverdi, A., (2004). New heuristics for m-machine no-wait flowshop to minimize total completion time. Omega, 32, 345–352. Atashpaz-Gargari, E., Lucas, C., (2007) Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. IEEE Congress, 4661–4670. Attar, S.F., Mohammadi, R., Tavakkoli-Moghaddam, M., (2011). A novel imperialist competitive algorithm to solve flexible flow shop scheduling problem in order to minimize maximum completion time, International Journal of Computer Applications, 28, 27-32. Chang, J.L., Gong, D.W., MA, X.P., (2007). A heuristic genetic algorithm for no-wait flowshop scheduling problem, Journal of China University of Mining and Technology, 17, 582–586. Chen, C., Neppalli, R., (1996). Genetic algorithms applied to the continuous flow shop problem. Computers and Industrial Engineering, 30, 919–929. Fink, A., Voß, S., (2003). Solving the continuous flow-shop scheduling problem by metaheuristics. European Journal of Operational Research, 151, 400–414. Hall, N.C., Sriskandarajah, C.A., (1996). Survey of machine scheduling problems with blocking and no-wait in process, Operations Research, 44, 510–525. Giaro, K., (2001). NP-hardness of compact scheduling in simplified open and flow shops, European Journal of Operational Research, 130, 90–98. Goyal, S.K., Sriskandarajah, C., (1998). No-wait shop scheduling: Computational complexity and approximate algorithms, Operations Research, 25, 220–244. Laha, D., Sapkal, S.U., (2014). An improved heuristic to minimize total flow time for scheduling in them-machine no-wait flow shop, Computers and Industrial Engineering, 67, 36-43.
زمانبندی جریان کاری ترکیبی با وجود کارهای بدون انتظار... 55
Naderi, B., Salmasi, N., (2012). Permutation flowshops in group scheduling with sequence-dependent setup times, European Journal of Industrial Engineering, 6(2), 177-199. Naderi, B., Khalili, M., Khamseh, A.A., (2014). Mathematical models and a hunting search algorithm for the no-wait flowshop scheduling with parallel machines, International Journal of Production Research, 52, 2667-2681. Nagano, M.S., da Silva, A.A., Lorena, L.A.N., (2014). An evolutionary clustering search for the no-wait flow shop problem with sequence dependent setup times, Expert Systems with Applications, 41, 3628-3633. Schuster, C.J., Framinan, J.M., Approximate procedure for no-wait job shop scheduling. Operations Research Letters, 31, 308–318. Rajendran, C., (1994). A no-wait flowshop scheduling heuristic to minimize makespan, Journal of the Operational Research Society, 45, 472–478. Röck, H., (1984). Some new results in flow shop scheduling, Mathematical Methods of Operations Research, 28, 1–16. Ruiz, R., Allahverdi, A., (2007). Some effective heuristics for no-wait flowshops with setup times to minimize total completion time, Annals of Operations Research, 156, 143–171. Pan, Q.K., Wang, L., Zhao, B.H., (2008). An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion, International Journal of Advanced Manufacturing Technology, 38, 778-786. Stafford, E.F., Tseng, F.T., Gupta, J.N.D., (2005). Comparative evaluation of MILP flowshop models, Journal of Operational Research Society, 56, 88–101. Tseng, F.T., Stafford, E.F., (2008). New MILP models for the permutation flowshop problem, Journal of the Operational Research Society, 59, 1373–1386.