Целочисленная модель с условиями оптимальности для задачи минимизации суммарного взвешенного времени обслуживания требований одним прибором

Целочисленная модель с условиями оптимальности для задачи минимизации суммарного взвешенного времени обслуживания требований одним прибором

Симанчёв Р. Ю., Уразова И. В.
Дискретный анализ и исследование операций, 32, 2, 122-136 (2025)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2025.32.818

Аннотация:

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

Табл. 3, ил. 2, библиогр. 10.

Литература:
  1. Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. Sequencing and scheduling: Algorithms and complexity // Logistics of production and inventory. Amsterdam: North-Holland, 1993. P. 445–522. (Handb. Oper. Res. Manag. Sci.; V. 4).
     
  2. Blazewicz J., Dror D., Weglarz J. Mathematical programming formulations for machine scheduling: A survey // Eur. J. Oper Res. 1991. V. 51, No. 3. P. 283–300.
     
  3. Симанчёв Р. Ю., Шерешик Н. Ю. Целочисленные модели обслуживания требований одним прибором с прерываниями // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 4. С. 89–101.
     
  4. Brucker P., Knust S. Complexity results for scheduling problems. Osnabrück: Osnabrück Univ., 2009. URL: mathematik.uni-osnabrueck.de/ research/OR/class (accessed: July 9, 2025).
     
  5. Шерешик Н. Ю. Релаксации многогранника оптимальных расписаний обслуживания требований одним прибором с прерываниями // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 6. С. 78–90.
     
  6. Simanchev R. Yu., Urazova I. V. Integer models for the total weighted tardiness problem on a single machine // Mathematical optimization theory and operations research: Recent trends. Rev. Sel. Pap. 22nd Int. Conf. (Yekaterinburg, Russia, July 2–8, 2023). Cham: Springer, 2023. P. 176–187. (Commun. Comput. Inf. Sci.; V. 1881). DOI: 10.1007/978-3-031-43257-6_14.
     
  7. Smith W. E. Various optimizers for single-stage production // Nav. Res. Logist. Q. 1956. V. 3, No. 1–2. P. 59–66. 
     
  8. Sauer N., Stone M. Preemptive scheduling // Algorithms and order. Dordrecht: Kluwer Acad. Publ., 1989. P. 307–323. (NATO Sci. Ser. C; V. 255).
     
  9. Баптист Ф., Карлье Ж., Кононов А. В., Керан М., Севастьянов С. В., Свириденко М. Структурные свойства оптимальных расписаний с прерыванием операций // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 1. С. 3–36.
     
  10. Лазарев А. А., Кварацхелия А. Г. Свойства оптимальных расписаний задачи теории расписаний минимизации суммарного взвешенного момента окончания для одного прибора // Автоматика и телемеханика. 2010. № 10. С. 80–89.

Исследование выполнено в рамках государственного задания Омского научного центра СО РАН (проекта № 121022000112–2). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Симанчёв Руслан Юрьевич
  1. Омский гос. университет им. Ф. М. Достоевского, 
    пр. Мира, 55а, 644077 Омск, Россия
  2. Омский научный центр СО РАН, 
    пр. Карла Маркса, 15, 644024 Омск, Россия

E-mail: osiman@rambler.ru

Уразова Инна Владимировна
  1. Омский гос. университет им. Ф. М. Достоевского, 
    пр. Мира, 55а, 644077 Омск, Россия

E-mail: urazovainn@mail.ru

Статья поступила 15 ноября 2024 г.
После доработки — 17 декабря 2024 г.
Принята к публикации 22 марта 2025 г.

Abstract:

The paper considers the following problem of scheduling theory. Jobs are serviced by a single machine. For each job, a positive weight and a release date are defined. The service durations are the same. Interruptions are allowed during service. Time is assumed to be discrete. It is necessary to find a schedule for servicing jobs that minimizes the weighted sum of end times of job processing. The complexity of the problem is currently unknown. This paper presents a new Boolean linear programming model for this problem, which includes certain necessary conditions for schedule optimality. These conditions are represented as linear inequalities. As a result of a computational experiment, it is noted that the model yields an integer solution even without imposing conditions on the variables to be integer. 

Tab. 3, illustr. 2, bibliogr. 10.

References:
  1. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, Sequencing and scheduling: Algorithms and complexity, in Logistics of Production and Inventory, (North-Holland, Amsterdam, 1993), pp. 445–522 (Handb. Oper. Res. Manag. Sci., Vol. 4).
     
  2. J. Blazewicz, D. Dror, and J. Weglarz, Mathematical programming formulations for machine scheduling: A survey, Eur. J. Oper Res. 51 (3), 283–300
     
  3. R. Yu. Simanchev and N. Yu. Shereshik, Integer models for the interruptoriented services of jobs by single machine, Diskretn. Anal. Issled. Oper. 21 (4), 89–101 (2014) [Russian].
     
  4. P. Brucker and S. Knust, Complexity results for scheduling problems (Osnabrück Univ., Osnabrück, 2009), URL: mathematik.uni-osnabrueck.de/ research/OR/class (accessed: July 9, 2025).
     
  5. N. Yu. Shereshik, Relaxations for the polyhedron of optimal schedules for the problem of interrupt-oriented service of jobs with a single machine, Diskretn. Anal. Issled. Oper. 22 (6), 78–90 (2015) [Russian].
     
  6. R. Yu. Simanchev and I. V. Urazova, Integer models for the total weighted tardiness problem on a single machine, in Mathematical Optimization Theory and Operations Research: Recent Trends (Rev. Sel. Pap. 22nd Int. Conf., Yekaterinburg, Russia, July 2–8, 2023) (Springer, Cham, 2023), pp. 176–187 (Commun. Comput. Inf. Sci., Vol. 1881), DOI: 10.1007/978-3-031-43257-6_14.
     
  7. W. E. Smith, Various optimizers for single-stage production, Nav. Res. Logist. Q. 3 (1–2), 59–66 (1956).
     
  8. N. Sauer and M. Stone, Preemptive scheduling, in Algorithms and Order, (Kluwer Acad. Publ., Dordrecht, 1989), pp. 307–323 (NATO Sci. Ser. C, Vol. 255).
     
  9. P. Baptiste, J. Carlier, A. V. Kononov, M. Queyranne, S. V. Sevastyanov, and M. Sviridenko, Structural properties of optimal schedules with preemption, Diskretn. Anal. Issled. Oper. 16 (1), 3–36 (2009) [Russian] [J. Appl. Ind. Math. 4 (4), 455–474 (2010)].
     
  10. A. A. Lazarev and A. G. Kvaratskheliya, Properties of optimal schedules for the minimization total weighted completion time in preemptive equallength job with release dates scheduling problem on a single machine, Avtom. Telemekh., No. 10, 80–89 (2010) [Russian] [Autom. Remote Control 71 (10), 2085–2092 (2010)].