Total weighted tardiness minimization for tasks with a common due date on parallel machines in case of agreeable weights and processing times

Abstract

We consider n tasks scheduling problem on m identical parallel machines by the criterion of minimizing the total weighted tardiness of tasks. All tasks arrive for processing at the same time. Weights and processing times are agreeable, that is, a greater weight of a task corre sponds to a shorter processing time. In addition, we have arbitrary start times of machines for tasks processing. The times may be less or greater than the due date or to coincide with it. The problem in this formulation is addressed for the first time. It can be used to provide planning and decision making in systems with a network representation of technological processes and limited resources. We give efficient PSC-algorithm with 𝑂(𝑚𝑛 log 𝑛) complexity that includes the polynomial component and the approximation algorithm based on permutations of tasks. The polynomial component contains sufficient signs of optimality of the obtained solutions and allows to obtain an exact solution by polynomial subalgorithm. In the case when the sufficient signs of optimality do not fulfill, we obtain approximate solution with an estimate of deviation from the optimum for each individual problem instance of any practical dimension. We show that a schedule obtained as a result of the problem solving can be split into two schedules: the schedule on machines which start time is less than or equal to the due date, and the schedule on machines which start after the due date. Optimization is only done in the first schedule. The second schedule is optimal by construction. Statistical studies of the PSC-algorithm showed its high efficiency. We solved problems with dimensions up to 40,000 tasks and up to 30 machines. The average time to solve the problem by the algorithm using the most efficient types of permutations was 27.3 ms for this dimension. The average frequency of an optimal solution obtaining amounted to 90.3 %. The average deviation from an optimum was no more than 0.000251.Розглядається задача складання розкладів виконання n завдань на m ідентичних паралельних приладах за критерієм мінімізації сумарного зваженого запізнення завдань. Всі завдання надходять на обслуговування одночасно. Ваги і тривалості узгоджені, тобто завданню з меншою тривалістю відповідає більша вага. Додатково, задані довільні моменти початку роботи приладів на виконання завдань, які можуть бути як менше директивного строку, так і більше, або співпадати з ним. У такій постановці задача розв'язується вперше. Вона може використовуватися для забезпечення планування та прийняття рішень в системах з мережним представленням технологічних процесів та обмеженими ресурсами. Наведено ефективний ПДС-алгоритм її розв'язання із трудомісткістю 𝑂(𝑚𝑛 log 𝑛), який включає поліноміальну складову з достатніми ознаками оптимальності одержуваних розв'язків, яка дозволяє отримувати точний розв'язок поліноміальним підалгоритмом. У разі невиконання достатніх ознак оптимальності ми отримуємо наближений розв'язок з оцінкою відхилення отриманого розв'язку від оптимального для кожної індивідуальної задачі будь-якої практичної розмірності. Показано, що розклад, отриманий в результаті розв'язання задачі, можна умовно розбити на два розклади – розклад на приладах, момент початку роботи яких менше або дорівнює директивному строку, та розклад на приладах, що починають роботу після директивного строку. Оптимізація виконується тільки у першому розкладі. Другий розклад оптимальний за побудовою. Статистичні дослідження ПДС-алгоритму показали його високу ефективність. Розв'язувались задачі з розмірністю до 40 000 завдань з числом приладів до 30. Середній час розв'язання задачі алгоритмом, що використовує найбільш ефективні типи перестановок, склав 27,3 мс при цій розмірності. Середня частота отримання оптимального розв'язку склала до 90,3 %. Середнє відхилення від оптимуму – не більш, ніж 0,000251.