RESEACH OF CHARACTERISTICS OF THE ALGORITHM IN SCHEDULING BY THE CRITERIA OF THE TOTAL EARLINESS-TARDINESS WITH ONE DEVICE ADJUSTMENT DEPENDING ON THE SEQUENCE

Author:

Melnyk Olena, State University «Uzhhorod National University», Uzhhorod, Ukraine

Language: ukrainian

Annotation:

We consider the one machine scheduling problems of minimizing the total earliness and tardiness of the tasks with one device adjustment depending on the sequence. Proposed heuristic algorithms are empirically evaluated in terms of their effectiveness. The results show that they generate in acceptable solutions that are sufficiently close to optimal.

Key words:

scheduling, one-stage problem, device adjustment, earliness, tardiness

References:

1. Згуровский М. З. Принятие решений в сетевых системах с ограниченными ресурсами : монография / М. З. Згуровский, А. А. Павлов. – К. : Наукова думка, 2010. – 573 с.

2. Павлов О. А. Дослідження властивостей та розв’язання задачі «Мінімізація сумарного штрафу як за випередження, так i за запізнення відносно директивних строків при виконанні незалежних завдань одним приладом» О. А. Павлов, О. Б. Місюра, О. В. Мельников // Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка : зб. наук. пр. − К. : ВЕК+, 2008. – № 48. – С. 3–6.

3. Складання розкладів сумарного випередження і запізнення із налагодженнями, що залежать від послідовності / Ф. Г. Ващук, О. А. Павлов, О. Б. Місюра, О. О. Мельник // Вісник Національного технічного університету України «КПІ». Інформатика, управління та обчислювальна техніка : зб. наук. пр. – К. : Век+, 2011. – № 53. – С. 192–194.

4. Baker K.R. Sequencing with earliness and tardiness penalties: a review / Baker K.R., Scudder G.D. // Operations Research. – 1990. – № 38 (1). – Р. 22–36.

5. Coleman B.J. A simple model for optimizing the single machine early/tardy problem with sequence dependent setups / B. JAY Coleman // Production and Operations Management. – 1992. – Vol. 1 (2). – P. 225–228.

6. Fisher M.L. A dual algorithm for the one-machine scheduling problem / Marshall L. Fisher // Mathematical Programming. – 1976. – Vol. 11 (1). – P. 229–251. 

7. Kanet J.J. Scheduling with inserted idle time: Problem taxonomy and literature review / Kanet J.J., Sridharan V. // Operations Research. – 2000. – № 48 (1). – Р. 99–110.

Download