OPTIMALITY BOX OF THE SCHEDULE MINIMIZING THE SUM OF THE WEIGHTED COMPLETION TIMES OF THE JOB
Abstract
It is proposed to use an optimality box of the job permutation π as a measure of the stability of an optimal permutation π for processing a set of jobs in the single-stage processing system respecting to variations of the processing times of the jobs. For randomly generated problems, experimental comparison is made of the relative dimensions and the volumes of the optimality box for permutation and relative errors of the objective function with the optimal value of the objective function calculated for the actual processing jobs.
About the Authors
Yu. N. Sotskov
United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk
Belarus
Belarus
N. G. Egorova
United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk
Belarus
Belarus
F. Werner
Otto-von-Guericke-University, Magdeburg
Germany
Germany
References
1. Optimization and approximation in deterministic sequencing and scheduling: a survey / R. L. Graham [et al.] // Ann. Discrete Math. – 1976. – Vol. 5. – P. 287–326.
2. Smith, W. E. Various optimizers for single-stage production / W. E. Smith // Naval Research Logistics Quarterly. – 1956. – Vol. 3, N 1. – Р. 59–66.
3. Scheduling under uncertainty: theory and algorithms / Yu. N. Sotskov [et al.]. – Minsk: Belorus. nauka, 2010.
4. Sotskov, Yu. N. Minimizing total weighted flow time of a set of jobs with interval processing times / Yu. N. Sotskov, N. G. Egorova, T.-C. Lai // Mathematical and Computer Modelling. – 2009. – Vol. 50, N 3/4. – P. 556–573.
5. Сотсков, Ю. Н. Многогранники устойчивости оптимальной перестановки обслуживания требований / Ю. Н. Сотсков, Н. Г. Егорова // Автоматика и телемеханика. – 2014. – № 7. – С. 136–154.
Review
Views: 711
Email this article 