Algorithms for approximate multi-stage Flow-Shop-Problem solution
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2019.3.09Keywords:
multi-stage schedules, flow-shop-problem, optimal sequences, lower bound of task execution time, approximate solution, heuristic algorithmAbstract
The construction of multi-stage schedules for performing tasks on machines located in a sequential chain has many practical applications in discrete-production scheduling. Estimates are obtained for the lower bound of the performance criterion for the optimal sequence of tasks and 2 algorithms for approximate problem solving, ensuring that all work is performed at all stages of processing in the shortest possible time. The algorithms of the solution are illustrated by a numerical example. The estimates of the complexity of the proposed algorithms are given. The given algorithms for solving the problem can be used in the scheduling of the small- and medium-sized discrete production.References
Konvej R.V. Teorija raspisanij / R.V. Konvej, V.L. Maksvell, L.V. Miller. — M.: Fizmatgiz, Nauka. 1975. — 359 s.
Zak Ju.A. Prikladnye zadachi teorii raspisanij i marshrutizatsii perevozok / Ju.A. Zak. — M.: URSS, 2012. — 394 s.
Zak Ju.A. Reshenie obobschennoj zadachi Dzhonsona s ogranichenijami na sroki vypolnenija zadanij i vremena raboty mashin. Ch.1. Tochnye metody reshenija / Ju.A. Zak // Problemy upravlenija. — 2010 — № 3. — S. 17–25. Ch. 2. Priblizhennye metody // Problemy upravlenija. — № 4. — 2010. — S. 12–19.
Zgurovskij M.Z. Prinjatie reshenij v setevyh sistemah s ogranichennymi resursami / M.Z. Zgurovskij, A.A. Pavlov. — K.: Nauk. dumka, 2010. — 573 s.
Johnson S.M. Optimal two- and three-stage production schedules with setup times included / S.M. Johnson // Naval research logistics quarterly. — 1954. — 1(1). P. 61–68.
Brucker P. Scheduling Algorithms / P. Brucker. — Berlin, Heidelberg und New York: Springer-Verlag, 1998.
Domschke W. Produktionsplanung. Ablauforganisatorische Aspekte / W. Domschke, A. Scholl, S. Voß. — Berlin, Heidelberg: Springer Verlag, 2005. — 456 p.
Ho J.C. A new heuristic for the n-job, M-machine problem / J.C. Ho, Y.-L. Chang // European Journal of Operational Research. — 1991. — 52. — P. 194–202.
Ogbu F.A. The application of the simulated annealing algorithm to the solution of the flow-shop problem / F.A. Ogbu, D.K. Smith // Computer & Operations Research. — 1990. — 17. — P. 243–253.
Hundal T.S. An extension of Palmer’s heuristic for the flow-shop scheduling problem / T.S. Hundal, J. Rajgopal // International Journal of Production Research. — 1988. — 26. — P. 1119–1124.
