МНОГОГРАННИК ОПТИМАЛЬНОСТИ РАСПИСАНИЯ, МИНИМИЗИРУЮЩЕГО СУММУ ВЗВЕШЕННЫХ МОМЕНТОВ ЗАВЕРШЕНИЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ

В качестве меры устойчивости оптимальной перестановки π обслуживания в одностадийной обслуживающей системе множества требований к изменениям длительностей обслуживания требований предлагается использовать размерность и относительный объем многогранника оптимальности перестановки π. Для случайно сгенерированных задач проведено экспериментальное сравнение размерностей и относительных объемов многогранников оптимальности расписаний обслуживания требований и относительных погрешностей целевых функций с оптимальными значениями целевых функций, вычисленными для фактических длительностей обслуживания требований. 

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.