A relaxation heuristic for scheduling flowshops with intermediate buffers

• Autorzy: Magiera M.
• Języki publikacji: EN

Abstrakty

EN

The paper presents a two-level relaxation heuristic for production planning for multistage flowshop systems with intermediate buffers. The method concerns unidirectional multistage systems where tasks with respect to many various types of products are performed simultaneously. The fixed and the alternative production routes are regarded in the method. The top-level is a stage loading, i.e., allocation of tasks among the stages. The base-level is a task scheduling - allocation of tasks among the stations. The linear mathematical models of mixed integer programming are used in the method. The time criterion is used in the minimization functions - the minimal schedule is fixed. The condition that variables are to be integers has been ignored in the heuristic. The relaxed heuristic developed in such a manner enables obtaining good results in a very short time. This paper discusses the multilevel approach as the developed production scheduling method serves the purpose of solving relatively large problems. Results of computational experiments with the proposed heuristic method are presented.

Słowa kluczowe

EN

scheduling; heuristic; linear programming; production planning; decision making; flowshop

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2013
• Tom: Vol. 61, nr 4
• Strony: 929--942
• Opis fizyczny: Bibliogr. 24 poz., rys., tab., diag.

Twórcy

autor

Magiera M.

• AGH University of Science and Technology, Faculty of Management, Department of Operations Research and Information Technology, 30 Mickiewicza Ave., 30-059 Cracow, Poland

Bibliografia

• [1] J. Błażewicz, K. Ecker, E. Pesch, G. Schmidt, and J. Węglarz, Handbook Scheduling, Springer, Berlin, 2007.
• [2] M. Pindeo, Scheduling: Theory, Algorithms, and Systems, Prentice Hall, Upper Saddle, 2002.
• [3] T. Sawik, Production Planning and Scheduling in Flexible Assembly Systems, Springer-Verlag, Berlin, 1999.
• [4] Y. Pochet and L.A. Wolsey, Production Planning by Mixed Integer Programming, Series in Operations Research and Financcical Engineering, Springer, New York, 2006.
• [5] G. Schmidt, “Modelling production scheduling systems”, Int. J. Production Economics 46-47, 109-118 (1996).
• [6] T. Sawik, “Simultaneous loading, routing, and assembly plan selection in a flexible assembly system”, Math. Comput. Modelling 28 (9), 19-29 (1998).
• [7] T. Sawik, “Balancing and scheduling or surface mount technology lines”, Int. J. Production Research 40 (9), 1973-1991 (2002).
• [8] T. Sawik, “Loading and scheduling of a flexible assembly system by mixed integer programming”, Eur. J. Operational Research 154 (1), 1-19 (2004).
• [9] T.F. Gonzales, Handbook of Approximation Algorithms and Metaheuristics, Chaoman and Hall/CRC, New York, 2007.
• [10] G. Schmidt, “Scheduling with limited machine availability”, Eur. J. Operational Research 121, 1-15 (2000).
• [11] T. Kis and E. Pesch, “A review of exact solution methods for the non-pre-emptive multiprocessor flowshop problem”, Eur. J. Operational Research 164 (3), 592-608 (2005).
• [12] I. Ribas, R. Leinstein, and J.M. Framinan, “Review and classification of hybrid flowshop scheduling problems from a production system and a solution procedure prespective”, Computers & Operations Resarch 37 (8), 1439-1454 (2010).
• [13] D. Quadt and H. Kuhn, “A taxonomy of flexible flow line scheduling procedures”, Eur. J. Operational Research 178 (3), 686-698 (2007).
• [14] R. Linn and W. Zhang, “Hybrid flow shop scheduling: a survey”, Computers & Industrial Engineering 37, 57-61 (1999).
• [15] R. Ruiz and J.A. V´azquez-Rodriguez, “The hybrid flow shop scheduling problem”, Eur. J. Operational Research 205 (1), 1-18 (2010).
• [16] M. Sterna, “Dominance relations for two-machine flow shop problem with late work criterion”, Bull. Pol. Ac.: Tech. 55 (1), 59-69, (2007).
• [17] M. Haouari, L. Hidri, and A. Gharbi, “Optimal scheduling of a two-stage hybrid flow shop”, Math. Meth. Operations Research 64 (1), 107-124 (2006).
• [18] H. Allaoui and A. Artiba, “Scheduling two-stage hybrid flow shop with availability constraints”, Computers & Operations Research 33 (5), 1399-1419 (2006).
• [19] Ch. Koulamas and G.J. Kyparisis, “ The three-stage assembly flowshop scheduling problem”, Computers & Operations Research 28 (7), 689-704 (2001).
• [20] T. Sawik, “Hierarchical approach to production scheduling in make-to-order assembly”, Int. J. Production Research 44 (4), 801-830 (2006).
• [21] M. Magiera, “Two-level of production scheduling for flow-shop systems with intermediate storages”, Total Logistic Management 1, 101-110 (2008).
• [22] R. Fourer, D. Gay, and B. Kernighan, AMPL, A Modelling Language for Mathematical Programming, Duxbury Press, Pacific Grove, 2003.
• [23] J. Kwiecień and B. Filipowicz, “Firefly algorithm in optimization of queuing systems”, Bull. Pol. Ac.: Tech. 60 (2), 363-368 (2012).
• [24] R. Nowotniak and J. Kucharski, “GPU-based tuning of quantum-inspired genetic algorithm for combinatorial optimization problem”, Bull. Pol. Ac.: Tech. 60 (2), 323-330 (2012).