Routing flow-shop with buffers and ready times - comparison of selected solution algorithms

• Autorzy: Józefczyk J. , Markowski M. , Balgabaeva L.

Identyfikatory

DOI

10.2478/mper-2014-0033

• Języki publikacji: EN

Abstrakty

EN

This article extends the former results concerning the routing flow-shop problem to minimize the makespan on the case with buffers, non-zero ready times and different speeds of machines. The corresponding combinatorial optimization problem is formulated. The exact as well as four heuristic solution algorithms are presented. The branch and bound approach is applied for the former one. The heuristic algorithms employ known constructive idea proposed for the former version of the problem as well as the Tabu Search metaheuristics. Moreover, the improvement procedure is proposed to enhance the quality of both heuristic algorithms. The conducted simulation experiments allow evaluating all algorithms. Firstly, the heuristic algorithms are compared with the exact one for small instances of the problem in terms of the criterion and execution times. Then, for larger instances, the heuristic algorithms are mutually compared. The case study regarding the maintenance of software products, given in the final part of the paper, illustrates the possibility to apply the results for real-world manufacturing systems.

Słowa kluczowe

EN

manufacturing systems; operations research; complex systems; optimization problems; scheduling algorithms; routing algorithms; heuristics; computer simulation

• Wydawca: Production Engineering Committee of the Polish Academy of Sciences ; Polish Association for Production Management
• Czasopismo: Management and Production Engineering Review
• Rocznik: 2014
• Tom: Vol. 5, No. 4
• Strony: 26--35
• Opis fizyczny: Bibliogr. 30 poz., rys., tab.

Twórcy

autor

Józefczyk J.

• Wroclaw University of Technology, Institute of Informatics, Wroclaw, Poland

autor

Markowski M.

• Wroclaw University of Technology, Institute of Informatics, Wroclaw, Poland

autor

Balgabaeva L.

• Kazakh Technical University, Department of Information Processing, Almaty, Kazakhstan

Bibliografia

• [1] Nagy G., Salhi S., Location-routing: Issues, models and methods, European Journal of Operational Research, 177, 649-672, 2007.
• [2] Prodhon C., A hybrid evolutionary algorithm for the periodic location-routing problem, European Journal of Operational Research, 210, 204-212, 2011.
• [3] Hamacher H.W., Hennes H., Integrated scheduling and location models: single machine makespan problems, Studies in Locational Analysis, 16, 77-90, 2007.
• [4] Kalsch M.T., Drezner Z., Solving scheduling and location problems in the plane simultaneously, Computerts & Operations Research, 37, 256-264, 2010.
• [5] Drezner Z., Scott C., Song, J.-S., The central warehouse location problem revisited, IMA Journal of Management Mathematics, 14, 321-336, 2003.
• [6] Li J., Chen H., Chu F., Performance evaluation of distribution strategies for the inventory routing problem, European Journal of Operational Research, 202, 412-419, 2010.
• [7] Moin N.H., Salhi S., Inventory routing problems: A logistical overview, Journal of the Operational Research Society, 58, 1185-1194, 2007.
• [8] Józefczyk J., Decision making problems in complex of operations systems (in Polish),Wroclaw,Wroclaw University of Technology Press, 2001.
• [9] Józefczyk J., Scheduling tasks on moving executors to minimize the maximum lateness, European Journal of Operational Research, 131, 171-187, 2001.
• [10] Averbakh I., Berman O., A simple heuristic for m-machine flow-shop and its applications in routingscheduling problems, Operations Research, 47, 165-170, 1999.
• [11] Metters R.D., Interdependent transportation and production activity at the United States postal service, Journal of the Operational Research Society, 47, 27-37, 1996.
• [12] Ben-Daya M., As’ad R., Seliaman M., An integrated production inventory model with raw material replenishment considerations in a three layer supply chain, International Journal of Production Economics, 143, 53-61, 2013.
• [13] Filcek G., Józefczyk J., Managing production and transportation in balanced supply networks, Systems Science, 35, 49-59, 2009.
• [14] Allahverdi A., Ng C.T., Cheng T.C.E., Kovalyov M.Y., A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187, 985-1032, 2008.
• [15] Ruiz R., Allahverdi A., No-wait flow shop with separate setup times to minimize maximum lateness, International Journal of Advanced Manufacturing Technology, 35, 551-565, 2007.
• [16] Ruiz R., Stutzle T., An iterated greedy heuristic for the sequence dependent setup times flow shop problem with makespan and weighted tardiness objectives, IRIDIA Technical Report, no. TR/IRIDIA/2006-02, 2006.
• [17] Rajendran C.H., Ziegler H., Scheduling to minimize the sum of weighted flow time and weighted tardiness of jobs in a flow shop with sequence - dependent setup times, European Journal of Operational Research, 149, 513-522, 2003.
• [18] Potts Ch.N., Kovalyov M.Y., Scheduling with batching: a review, European Journal of Operational Research, 120, 228-249, 2000.
• [19] Thomas W., Algorithms for task scheduling with moving executors to minimize the mean flow time [in Polish], PhD Thesis, Technical Report of the Faculty of Computer Science and Management, Wroclaw University of Technology, PRE/2, 2006.
• [20] Józefczyk J., Markowski M.: Integrated optimization problems in operations research, Analysis and decision making for complex and uncertain systems, Proceedings of 23rd Int. Conf. on Systems Research, Informatics and Cybernetics, Baden-Baden, Germany, 1, 39-43, 2011.
• [21] Yu W., Liu Z., Wang L., Fan T., Routing open shop and flow shop scheduling problems, European Journal of Operational Research, 213, 24-36, 2011.
• [22] Averbakh I., Berman O., Chernykh I., A 6/5 - approximation algorithm for the two-machine routing open-shop problem on a two-node network, European Journal of Operational Research, 166, 3-24, 2005.
• [23] Józefczyk J., Markowski M., Heuristic algorithms for solving uncertain routing-scheduling problem, Lecture Notes in Computer Science, 5097, 1052-1063, 2008.
• [24] Józefczyk J., Markowski M., Simulated annealing based robust algorithm for routing-scheduling problem with uncertain execution times, Proceedings of 13th IFAC Symposium on Information Control Problems in Manufacturing, INCOM ’09, Moscow, Russia, pp. 1985-990, 2009.
• [25] Cheng J., Steiner G. Stephenson P., A computational study with a new algorithm for the threemachine permutation flow-shop problem with release times, European Journal of Operational Research, 130, 559-575, 2001.
• [26] Framinan J.M., Gupta J.N.D., Leisten R., A review and classification of heuristics for permutation flowshop scheduling with makespan objective, Journal of the Operational Research Society, 55, 1243-1255, 2004.
• [27] Rebaine D., Flow shop vs. permutation shop with time delays, Computers & Industrial Engineering, 48, 357-362, 2005.
• [28] Pinedo M.L., Scheduling theory, algorithms and systems, New York, Springer, 2008.
• [29] Józefczyk J., Markowski M., Heuristic solution algorithm for routing flow shop with buffers and ready times, Analysis and decision making for complex and uncertain systems, Proceedings of 24th Int. Conf. on Systems Research, Informatics and Cybernetics, Baden-Baden, Germany, 2, 37-41, 2012.
• [30] Golden B., Bodin L., Doyle T., Stewart W. Jr., Approximate traveling salesman algorithms, Operational Research, 28, 3, Part II, 694-711, 1980.