Evolutionary Algorithm for Minmax Regret Flow-Shop Problem

• Autorzy: Michał Ćwik , Jerzy Józefczyk
• Języki publikacji: EN

Abstrakty

EN

The uncertain flow-shop is considered. It is assumed that processing times are not given a priori, but they belong to intervals of known bounds. The absolute regret (regret) is used to evaluate a solution (a schedule) which gives the minmax regret binary optimization problem. The evolutionary heuristic solution algorithm is experimentally compared with a simple middle interval heuristic algorithm for three machines instances. The conducted simulations confirmed the several percent advantage of the evolutionary approach. (original abstract)

Słowa kluczowe

EN

Algorithms; Simulation; Manufacturing technologies

PL

Algorytmy; Symulacja; Technologie wytwarzania

• Czasopismo: Management and Production Engineering Review
• Rocznik: 2015
• Tom: 6
• Numer: nr 3
• Strony: 3--9

Twórcy

autor

Michał Ćwik

• Wroclaw University of Technology

autor

Jerzy Józefczyk

• Wroclaw University of Technology

Bibliografia

• [1] Pinedo M.L., Scheduling - Theory, Algorithms and Systems, Springer, 2008.
• [2] Dutt L.S., Kurian M., Handling of Uncertainty - A Survey, International Journal of Scientific and Research Publications, 3, 2250-315, 2013.
• [3] Pinedo M.L., Schrage L., Stochastic shop scheduling: A survey, Dempster M.A.H., Lenstra J.K., Rinooy Kann A.H.G. [Eds.], Deterministic and Stochastic Scheduling, Reidel, Dordrecht, 1982.
• [4] Kouvelis P., Yu G., Robust Discrete Optimization and its Applications, Kluwer Academic Publishers, Dordrecht-Boston-London, 1997.
• [5] Conde E., A 2-approximation for minmax regret problems via a mid-point scenario optimal solution, Operations Research Letters, 38 (4), 326-327, 2010.
• [6] Averbakh I., Minimax regret solutions for minimax optimization problems with uncertainty, European Journal of Operational Research, 27 (2), 57-65, 2000.
• [7] Kasperski A., Zielinski P., A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion, Operations Research Letters, 42, 343-344, 2008.
• [8] Aissi H., Bazgan C., Vanderpooten D., Min-max and min-max regret versions of combinatorial optimization problems: A survey, European Journal of Operational Research, 197 (2), 427-438, 2009.
• [9] Siepak M., Józefczyk J., Solution algorithms for unrelated machines minmax regret scheduling problem with interval processing times and the total flow time criterion, Annals of Operations Research, 222, 517533, 2014.
• [10] Kasperski A., Kurpisz A., Zielinski P. Approximating a two-machine flow shop scheduling under discrete scenario uncertainty, Journal of Operational Research, 217, 36-43, 2012.
• [11] Averbakh I., The minmax regret permutation flow-shop problem with two jobs, Operations Research Letters, 69 (3), 761-766, 2006.
• [12] Garey M.R., Johnson D.S., Sethi R., The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 117-129, 1976.
• [13] Lebedev V., Averbakh I., Complexity of minimizing the total flow time with interval data and minmax regret criterion, Discrete Applied Mathematics, 154, 2167-2177, 2006.
• [14] Nawaz M., Enscore Jr. E., Ham I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, The International Journal of Management Science, 11, 91-95, 1983.

Identyfikatory

DOI

10.1515/mper-2015-0021