ПДС-алгоритмы решения задач составления расписаний по критерию опережения/запаздывания на одном приборе
Анотація
Предложены эффективные ПДС-алгоритмы решения NP-трудной задачи опережения/запаздывания для
случаев, когда момент начала выполнения заданий фиксирован или находится в интервале времени [t1, tk].
Решение основано на ПДС-алгоритме решения задачи минимизации суммарного запаздывания заданий.
Разработан эвристический алгоритм определения самого позднего момента начала выполнения заданий,
при котором достигается минимальное значение функционала. Приведены примеры решения задач и ре-
зультаты экспериментальных исследований.
Посилання
ПДС-алгоритмы решения задач составления расписаний по критерию
опережения/запаздывания на одном приборе
Feldmann M., Biskup D. Single–machine scheduling for minimizing earliness and tardiness penalties by meta–
heuristic approaches // Computers & Industrial Engineering.– 2003.– №44.– P.307–323
Tϋtϋncϋoglu R.A. Sequencing with earliness and tardiness penalties.– Department of Industrial Engineering,
Bilkent University, 1999.– 14 p.
Valente J. M. S., Alves R. A. F. S. Improved heuristics for the early/tardy scheduling problem with no idle time //
Computers & Operations Research.– 2005.– №32.– P.557–569
Jin S., Mason S.J. Minimizing earliness and tardiness costs on a single machine with uncommon job due dates //
Department of Industrial Engineering, Bell Engineering Center, University of Arkansas Fayetteville, 2004.– 23
p.
Павлов А.А., Мисюра Е.Б., Лисецкий Т.Н., Сперкач М.О., Халус Е.А. Четырехуровневая модель планиро-
вания, принятия решений и оперативного управления в сетевых системах с ограниченными ресурсами //
Вісник НТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.: “ВЕК+”, 2013. –
№58 –с. 11–23.
Kanett J.J. Minimizing the average deviation of job completion times about a common due date // Nav Res
Logist // Naval Research Logistics. – 1981. – №28. – P. 643–651.
Lawler E.L. A fully polynomial approximation scheme for the total tardiness problem [Текст] / E.L. Lawler //
Operations Research Letters. – 1982. – №1. – Р.207–208
Baker K.R. Sequencing with earliness and tardiness penalties: a review [Текст] / K.R. Baker, G.D. Scudder //
Operations Research. – 1990. – Vol.1. – №38. – Р.22–36.
T’kindt V., Billaut J.–C. Multicriteria scheduling: theory, models and algorithms: Springer, Berlin; Heidelberg,
New York. – 2002.
Garey M.R. One–processor scheduling with symmetric earliness and tardiness penalties [Текст] / M.R. Garey, R.E.
Tarjan, G.T. Wilfong // Mathematics of Operations Research. – 1988. – №13. – Р.330–348.
Yano C.A. Algorithms for a class of single–machine weighted tardiness and earliness problems [Текст] / C.A.
Yano, Y.D. Kim // European Journal of Operations Research. – 1991. – Vol.52. – Р.167–178.
Ow P.S. The single machine early/tardy problem [Текст] / P.S. Ow, T.E. Morton // Management Science. –
– Vol.2. – №35. – Р.177–191.
Davis J.S. Single–machine scheduling with early and tardy completion costs [Текст] / J.S. Davis, J.J. Kanet //
Naval Research Logistics. – 1993. – №40.– Р. 85–101.
Szwarc W. Optimal timing scheduling in earliness–tardiness single machine sequencing
Sridharan V. A decision theory based scheduling procedure for single–machine weighted earliness and tardiness
problem [Текст] // V. Sridharan, Z. Zhou // European Journal of Operations Research. – 1996. – Vol.94. –
Р.292–301.
G., Yen B.P.C. Tabu search for single–machine scheduling with distinct due windows and weighted earliness/
tardiness penalties // European Journal of Operations Research. – №142. – 2002. – P.271–281
Szwarc W. Adjacent ordering in single–machine scheduling with earliness and tardiness penalties // Naval Research
Logistics. – 1993. – №40. – P.229–243
Lee C.Y., Choi J.Y. A generic algorithm for job sequencing problem with distinct due dates and general early–
tardy penalty weights // Computers & Operational Research. – 1995. – №22. – P.857–869.
Bank J., Werner F. Heuristic algorithm for unrelated parallel machine scheduling with a common due date, release
dates, and linear earliness and tardiness penalties // Math Comput Model. – 2001. – №33. – P.363–383.
Gordon V., Proth J.P., Chu C. A survey of the state–of–art of common due date assignment and scheduling research
// European Journal of Operations Research. – 2002. – №139. – P.1–25
Valente J.M.S., Alves R.A.F.S. Filtered and recovering beam search algorithms for the early/tardy scheduling problem
with no idle time // Computers & Industrial Engineering. – 2005. – №48(2) . – P.363–375
Tung–I Tsai. A genetic algorithm for solving the single machine earliness/tardiness problem with distinct due
dates and ready times // International Journal of Advanced Manufacturing Technologies. – 2007. – №32. –
P.994–1000
Hoogeveen J.A., Van de Velde L.S. A branch–and–bound algorithm for single–machine earliness–tardiness
scheduling with idle time // INFORMS Journal of Computing. – 1996. – №8. – P.402–412.
Згуровский М.З., Павлов А.А. Принятие решений в сетевых системах с ограниченными ресурсами: Мо-
нография.– К.: Наукова думка, – 2010.– 573 с.
Павлов О.А., Місюра О.Б., Шевченко К.Ю. Побудова ПДС-алгоритму розв’язання задачі мінімізації
сумарного зваженого запізнення виконання робіт на одному приладі // Вісник НТУУ “КПІ”. Серія «Інформа-
тика, управління та обчислювальна техніка». – К.: “ВЕК+”, 2012. – №56.– С. 58–70.
Павлов А.А., Мисюра Е.Б., Костик Д.Ю. Минимизация суммарного запаздывания при наличии заданий с
отрицательными значениями директивных сроков // Вісник НТУУ “КПІ”. Серія «Інформатика, управлін-
ня та обчислювальна техніка». – К.: “ВЕК+”, 2011. – №53.– С.3–5.
