Efficient Exact Minimization of Total Tardiness in Tight-Tardy Progressive Single Machine Scheduling with Idling-Free Preemptions of Equal-Length Jobs

Скорочена інформація про документ
dc.contributor.authorRomanuke, V. V.
dc.date.accessioned2021-03-30T11:16:18Z
dc.date.available2021-03-30T11:16:18Z
dc.date.issued2020
dc.description.abstractenBackground. A schedule ensuring the exactly minimal total tardiness can be found with the respective integer linear programming problem. An open question is whether the exact schedule computation time changes if the job release dates are input to the model in reverse order. Objective. The goal is to ascertain whether the job order in tight-tardy progressive single machine scheduling with idling-free preemptions of equal-length jobs influences the speed of computing the exact solution. The Boolean linear programming model provided for finding schedules with the minimal total tardiness is used. Methods. To achieve the said goal, a computational study is carried out with a purpose to estimate the averaged computation time for both ascending and descending orders of job release dates. Instances of the job scheduling problem are generated so, that schedules which can be obtained trivially, without the exact model, are excluded. Results. Based on the three-dimensional barred plot of the relative difference between the averaged computation times, it has been shown that a possibility exists to find schedules more efficiently by manipulating the job order. For instance, schedules of 5 jobs consisting of two processing periods each are found on average by 14.67 % faster for the descending job order. In another example of 7 three-parted jobs, an optimal schedule is found on average in 69.51 seconds by the ascending job order, whereas the descending job order takes just 36.52 seconds to find it, saving thus 32.99 seconds. Conclusions. Scheduling a fewer jobs divided into a fewer job parts is executed on average faster by the descending job order. As the number of jobs increases along with increasing the number of their processing periods, the ascending job order becomes more efficient. However, the computation time efficiency by both job orders tends to be irregular.uk
dc.description.abstractruПроблематика. Расписание, обеспечивающее строго минимальное общее запаздывание, можно найти по соответствующей целочисленной задаче линейного программирования. Открытым является вопрос о том, меняется ли время вычисления точного расписания, если даты запуска заданий вводятся в модель в обратном порядке. Цель исследования. Цель состоит в том, чтобы установить, влияет ли на скорость вычисления точного решения порядок заданий в плотном прогрессирующем одномашинном планировании равноценных заданий с переключениями без простоя. Для поиска расписаний с минимальным общим запаздыванием используется модель булевого линейного программирования. Методика реализации. Для достижения указанной цели проводится вычислительное исследование с целью оценки усредненного времени вычисления как для восходящего порядка, так и для нисходящего порядка дат запуска заданий. Примеры задачи планирования заданий генерируются так, что расписания, которые можно получить тривиально, без точной модели, не рассматриваются. Результаты исследования. На основе трехмерного брусоподобного графика относительной разности между усредненными временами вычислений было показано, что существует возможность более эффективного поиска расписаний путем манипулирования порядком заданий. Например, расписания 5-ти заданий, состоящих из двух периодов обработки, в среднем находятся на 14,67 % быстрее для нисходящего порядка заданий. В другом примере из 7-ми заданий, состоящих из трех частей каждое, оптимальное расписание находится в среднем за 69,51 секунды при восходящем порядке заданий, тогда как для нисходящего порядка заданий нужно лишь 36,52 секунды, что экономит 32,99 секунды. Выводы. Планирование меньшего количества заданий, разделенных на меньшее количество частей, выполняется в среднем быстрее при нисходящем порядке заданий. Как только количество заданий увеличивается вместе с увеличением количества периодов их обработки, восходящий порядок заданий становится более эффективным. Однако эффективность времени вычисления при обоих порядках заданий имеет тенденцию к нерегулярности.uk
dc.description.abstractukПроблематика. Розклад, що забезпечує строго мінімальне загальне запізнювання, можна знайти за відповідною цілочисловою задачею лінійного програмування. Відкритим є питання про те, чи змінюється час обчислення точного розкладу, якщо дати запуску завдань вводяться в модель у зворотному порядку. Мета дослідження. Мета полягає у тому, щоб встановити, чи впливає на швидкість обчислення точного розв’язку порядок завдань у щільному прогресуючому одномашинному плануванні рівноцінних завдань із перемиканнями без простою. Для пошуку розкладів із мінімальним загальним запізнюванням використовується модель булевого лінійного програмування. Методика реалізації. Для досягнення зазначеної мети проводиться обчислювальне дослідження з метою оцінки усередненого часу обчислення як для висхідного порядку, так і для спадного порядку дат запуску завдань. Приклади задачі планування завдань генеруються так, що розклади, які можна отримати тривіально, без точної моделі, не розглядаються. Результати дослідження. На основі тривимірного брусоподібного графіка відносної різниці між усередненими часами обчислень було показано, що існує можливість більш ефективного пошуку розкладів завдяки маніпулюванню порядком завдань. Наприклад, розклади 5-ти завдань, що складаються з двох періодів обробки, в середньому знаходяться на 14,67 % швидше для спадного порядку завдань. В іншому прикладі з 7-ми завдань, що складаються з трьох частин кожне, оптимальний розклад знаходиться в середньому за 69,51 секунди за висхідного порядку завдань, тоді як для спадного порядку завдань потрібно лише 36,52 секунди, що заощаджує 32,99 секунди. Висновки. Планування меншої кількості завдань, розділених на меншу кількість частин, виконується в середньому швидше за спадного порядку завдань. Щойно кількість завдань збільшується разом зі збільшенням кількості періодів їх обробки, висхідний порядок завдань стає більш ефективним. Однак ефективність часу обчислення за обома порядками завдань має тенденцію до нерегулярності.uk
dc.format.pagerangePp. 27-39uk
dc.identifier.citationRomanuke, V. V. Efficient Exact Minimization of Total Tardiness in Tight-Tardy Progressive Single Machine Scheduling with Idling-Free Preemptions of Equal-Length Jobs / V. V. Romanuke // Наукові вісті КПІ : міжнародний науково-технічний журнал. – 2020. – № 1(128). – С. 27–39. – Бібліогр.: 9 назв.uk
dc.identifier.doihttps://doi.org/10.20535/kpi-sn.2020.1.180877
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/40332
dc.language.isoenuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.relation.ispartofНаукові вісті КПІ : міжнародний науково-технічний журнал, 2020, № 1(128)uk
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.subjectjob schedulinguk
dc.subjectpreemptive single machine schedulinguk
dc.subjectexact modeluk
dc.subjecttotal tardinessuk
dc.subjectcomputation timeuk
dc.subjectascending job orderuk
dc.subjectdescending job orderuk
dc.subjectпланування завданьuk
dc.subjectпланування на одній машині з перемиканнямиuk
dc.subjectточна модельuk
dc.subjectзагальне запізнюванняuk
dc.subjectчас обчисленняuk
dc.subjectвисхідний порядок завданьuk
dc.subjectспадний порядок завданьuk
dc.subjectпланирование заданийuk
dc.subjectпланирование на одной машине с переключениямиuk
dc.subjectточная модельuk
dc.subjectобщее запаздываниеuk
dc.subjectвремя вычисленияuk
dc.subjectвосходящий порядок заданийuk
dc.subjectнисходящий порядок заданийuk
dc.subject.udc519.161+519.852+519.687.1uk
dc.titleEfficient Exact Minimization of Total Tardiness in Tight-Tardy Progressive Single Machine Scheduling with Idling-Free Preemptions of Equal-Length Jobsuk
dc.title.alternativeЕфективна точна мінімізація загального запізнювання у щільному прогресуючому одномашинному плануванні рівноцінних завдань із перемиканнями без простоюuk
dc.title.alternativeЭффективная точная минимизация общего запаздывания в плотном прогрессирующем одномашинном планировании равноценных заданий с переключениями без простояuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
NVKPI2020-1_04.pdf
Розмір:
639.91 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.01 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Наукові вісті КПІ: міжнародний науково-технічний журнал, № 1(128)