Heuristic algorithms for constructing effective sequences of tasks on one machine in interconnected production systems
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2020.1.09Keywords:
task execution sequences, multistage schedules, minimum time, heuristic algorithm, lower bound on the value of the optimality criterionAbstract
The classical task in the theory of scheduling which is the task of constructing a sequence of tasks on one machine, taking into account not only the time spent on equipment operation, but also the loss of post-processing, is considered for multi-stage production systems consisting of an interconnected chain of sections and workshops of an industrial enterprise. As an optimality criterion, the implementation of a multi-stage schedule in the shortest possible time is considered. Methods are proposed for calculating the lower bound on the length of the optimal pattern along with heuristic algorithms for obtaining approximate solutions that require small amounts of computation. The proposed algorithms are illustrated by numerical examples.References
Conway R.W. Theory of Scheduling / R.W. Conway, W.L. Maxwell, L.W. Miller. — Addison-Wesley Publishing Company, 1967. — 294 p.
Zack Yu.A. Applied problems of the theory of scheduling and traffic routing [in Russian] / Yu.A. Zack. — M., URSS, 2012. — 394 p.
Zgurovsky M.Z. Decision making in networked systems with limited resources [in Russian] / M.Z. Zgurovsky, A.A. Pavlov. — K.:. Nauk. dumka, 2010. — 573 p.
Zack Yu.A. Construction of two-stage schedules of processing of products on one machine / Yu.A. Zack // System research and information technologies. — 2018. — № 4. — P. 19–36.
Zack Yu.A. Developing admissible and optimal schedules of works on one machine / Yu.A. Zack // Cybernetics and systems analysis. — № 1. — 2012.
Zak Yu.A. Two-stage planning tasks for the flow line / Yu.A. Zak // Control Sciences. — M., 2019. — № 6. — P. 52–62.
Zack Yu.A. Algorithms for approximate multi-stage Flow-Shop-Problem solution / Yu.A. Zack // System research and information technologies. — 2019. — № 3. — P. 100–109.
Carlier J. The one-machine sequencing problem / J. Carlier // European Journal of Operational Research. — 1982. — N 11. — P. 42–47.
Domschke W. Produktionsplanung. Ablauforganisatorische Aspekte / W. Domschke, A. Scholl, S. Voß. — Berlin, Heidelberg: Springer Verlag, 2005. — 456 p.
Brucker P. Scheduling Algorithms / P. Brucker // Springer-Verlag, Berlin, Heidelberg und New York, 1998. — 377 p.
Sidorenko A.M. Work planning and scheduling subject to modules and articles assembly / A.M. Sidorenko, E.N. Khobotov // Automation in industry. — 2012. — № 10. — P. 21–25.
Zak Ju.A. Properties of admissible and optimum sequences of performance of works on a single machine / Ju.A. Zak // Control Sciences. — 2012. — № 5. — P. 54–61.
