?
Special Case of the Single Machine Total Tardiness Problem Is NP-Hard
.
Lazarev A. A., Gafarov E.
In this paper we show that the special case {\bf B-1} (Lazarev et al., 2004) of the single machine total tardiness problem $1||\sumT_j$ is NP-hard in the ordinary sense. For the case we have constructed pseudo-polynomial algorithm $O(n\sum p_j)$ time.
Language:
English
In book
Saint Etienne : [б.и.], 2006
Lazarev A. A., Kvaratskhelia A., Автоматика и телемеханика 2010 № 10 С. 80-89
In this paper, we consider the minimizing total weighted completion time in preemptive equal-length job with release dates scheduling problem on a single machine. This problem is known to be open. Here, we give some properties of optimal schedules for the problem and its special cases. ...
Added: November 24, 2012
Lazarev A. A., Arkhipov D. I., Amsterdam : University of Amsterdam, 2011
We study the scheduling problem for single machine with preemptions of jobs. On a machine it is necessary to process a set of n jobs. Simultaneous processing is prohibited, but interrupts in processing jobs is possible. Each job j of the set is characterize by it's weight w_j, release date r_j = j - 1 ...
Added: March 4, 2013
Lazarev A. A., Gafarov E., , in : IFAC Symposium on Information Control Problems in Manufacturing (2009). : M. : [б.и.], 2009. P. 1512-1515.
We consider some special cases of the NP-hard resource-constrained projects cheduling problem (RCPSP) to minimize the makespan. We show that a well-known lowerbounds for the problem may yield bad approximation ratios or its calculation is an NP-hardproblem too. We conjecture that the ratio of the optimal makespan of RCPSP to that of the preemptive version ...
Added: March 4, 2013
Lazarev A. A., В кн. : Московская международная конференция по Исследованию операций. : М. : [б.и.], 2007.
Мы рассматриваем подход к построению приближённого решения с гарантированной абсолютной погрешностью для NP-трудных задач теории расписаний минимизации максимального временного смещения. ...
Added: March 4, 2013
Lazarev A. A., Korenev P. S., В кн. : Труды третьей российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения»: труды и пленарные доклады участников конференции УКИ`12. : М. : ИПУ РАН, 2012. С. 267-274.
Задачи формирования составов и расписания движения грузовых поездов могут быть сформулированы как задач и теории расписаний. Многие из этих задач являются NP-трудными, в связи с чем возникает проблема поиска приближенного решения таких задач. Предлагается метод, основанный на введении метрики для пространства параметров задачи, позволяющий за полиномиальное время находить решение задачи с гарантированной абсолютной погрешностью целевой ...
Added: December 30, 2012
Lazarev A. A., Musatova E. G., Ласкова М. В., В кн. : Труды третьей российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения»: труды и пленарные доклады участников конференции УКИ`12. : М. : ИПУ РАН, 2012. С. 1968-1973.
Рассматривается задача составления плана движения грузовых составов между двумя станциями, соединенными одноколейной железной дорогой. Предлагается эвристический алгоритм решения поставленной задачи, минимизирующий суммарное запаздывание прибытия грузовых составов. ...
Added: March 4, 2013
Gafarov E., Lazarev A. A., Werner F., / Otto-von-Guericke Universitaet. 2010. No. 10.
In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. An NP-hardness proof and a pseudo-polynomial time solution algorithm are proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted ...
Added: March 4, 2013
Lazarev A. A., Baranov A. V., Amsterdam : University of Amsterdam, 2011
Added: March 4, 2013
Lazarev A. A., Gafarov E., М. : Вычислительный центр им. А.А. Дородницына РАН, 2007
Рассматривается задача построения расписания проекта с учетом ограничений на ресурсы и ее частные случаи. Приводятся результаты исследования известных нижних оценок. Выдвинута гипотеза о свойствах оптимального значения целевой функции в задаче с прерываниями и без прерываний обслуживания требований и представлено доказательство гипотезы для частных случаев задачи. Показано, что любой проект можно преобразовать в проект с "планарным" ...
Added: December 17, 2012
Lazarev A. A., Скиндерев С., В кн. : Московская международная конференция по Исследованию операций. : М. : [б.и.], 2007.
Были рассмотрены некоторые частные (NP-трудные) случаи задач теории расписаний. Предлагаются схемы нахождения приближённого решения для всех этих случаев, т.е. для любого исходного примера строится решение с гарантированной абсолютной погрешностью значения целевой функции. ...
Added: March 4, 2013
Lazarev A. A., Gafarov E., Доклады Академии наук 2008 Т. 424 № 1 С. 7-9
27.47.19 Исследование операций
28.15.19 Нелинейные детерминированные системы
28.19.15 Оптимальные системы
28.29.15 Методы исследования операций ...
Added: November 23, 2012
Lazarev A. A., Садыков Р. Р., М. : Вычислительный центр им. А.А. Дородницына РАН, 2007
Рассматриваются классические NP-трудные задачи теории расписаний для одного прибора: минимизация максимального временного смещения (1 | rj | Lmax) и суммарного взвешенного числа запаздывающих требований (1 | rj | ΣwjUj). Исследуемые задачи являются схематичными теоретическими моделями практических задач. Алгоритмы для решения этих задач используются как вспомогательные для решения более сложных задач теории расписаний, приближенных к практике. ...
Added: December 17, 2012
Lazarev A. A., М. : Московский физико-технический институт, 2008
Рассматриваются классические NP-трудные задачи теории расписаний для одного и нескольких приборов с критерием минимизации максимального временного смещения и быстродействия. Предлагается качественно новая схема нахождения приближённого решения. Вводится понятие метрики (расстояния) между примерами задачи. Идея предлагаемого подхода состоит в построении по исходному примеру задачи другого примера, для которого удаётся найти оптимальное или приближённое решение с минимальным ...
Added: December 17, 2012
Lazarev A. A., Gafarov E., , in : Multidisciplinary International Conference on Scheduling: Theory and Application, Paris, France, 2009. : Dublin : [б.и.], 2009.
We consider some special cases of the NP-hard resource-constrained projectscheduling problem (RCPSP) to minimize the makespan. We conjecture that the ratioof the optimal makespan of RCPSP to that of the preemptive version of the problemis less than 2. We show that a well-known lower bounds for the problem may yield badapproximation ratios or its calculation ...
Added: March 4, 2013
Kvaratskhelia A., Lazarev A. A., , in : Multidisciplinary International Conference on Scheduling: Theory and Application, Paris, France, 2009. : Dublin : [б.и.], 2009. P. 68-76.
In this paper, we consider the minimizing total weighted completion time inpreemptive equal-length job with release dates scheduling problem on a single machine. Before this paper the problem is known to be open. Here, we present a polynomial timealgorithm that solves the problem with O(n^7) operations. ...
Added: March 4, 2013
Lazarev A. A., Журнал вычислительной математики и математической физики 2007 Т. 47 № 6 С. 1087-1099
The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding ...
Added: November 23, 2012
Lazarev A. A., В кн. : Труды третьей российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения»: труды и пленарные доклады участников конференции УКИ`12. : М. : ИПУ РАН, 2012. С. 371-380.
В статье представлены новые модели задач, возникающих в области маршрутизации железнодорожного грузового транспорта, формирования составов и графиков их движения. Предлагаются точные полиномиальные алгоритмы решения частных случаев сформулированных задач. ...
Added: December 29, 2012
Gafarov E., Lazarev A. A., Information Processing Letters 2012 Т. 112 № 3 С. 72-76
In this note, we consider a single machine scheduling problem with generalized total tardiness objective function.
A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new
graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number
of tardy jobs on a single ...
Added: November 24, 2012
Gafarov E., Lazarev A. A., Werner F., Mathematical Social Sciences 2011 No. 62 P. 7-13
We consider single machine scheduling problems with a non-renewable resource. These types of problems have not been intensively investigated in the literature so far. For several problems of these types with standard objective functions (namely the minimization of makespan, total tardiness, number of tardy jobs, total completion time and maximum lateness), we present some complexity ...
Added: November 24, 2012
Lazarev A. A., , in : European Chapter on Combinatorial Optimization (ECCO 2009). : Jerusalem : [б.и.], 2009. P. 13-13.
In this paper, for $NP$-hardness single and multi-machine scheduling problems with the criterion of minimization maximum lateness the metrics $\rho$ has been used. We consider some approaches finding of the approximate solution for the problems. The idea of approaches consists in construction to a initial instance $A$ such instance $B$ (with the same number of ...
Added: March 4, 2013
Gafarov E., Lazarev A. A., Werner F., Annals of Operations Research 2012 Vol. 196 No. 1 P. 247-261
We consider the problem of maximizing total tardiness on a single machine, where the first job starts at time zero and idle times between the processing of jobs are not allowed.We present a modification of an exact pseudo-polynomial algorithm based on a graphical approach, which has a polynomial running time. This result settles the complexity ...
Added: November 24, 2012
Lazarev A. A., Kvaratskhelia A., , in : Optimization and applications (OPTIMA-2009). : M. : -, 2009. P. 58-59.
In this paper, we propose an approach for obtaining metrics for a variety of scheduling problems. ...
Added: March 4, 2013
Lazarev A. A., Arkhipov D. I., , in : 28th Conference of the European Chapter on Combinatorial Optimization. : Катания : University of Catania, 2015. P. 64.
The following classical NP-complete scheduling problem is considered. ...
Added: June 22, 2015
Gafarov E., Lazarev A. A., Werner F., / Otto-von-Guericke Universitaet. 2010. No. 12.
In this paper, we consider the problem of maximizing total tardiness on a single machine, where the first job starts at time zero and idle times between the processing of jobs are not allowed. We present a modification of an exact pseudo-polynomial algorithm based on a graphical approach, which has a polynomial running time. ...
Added: March 4, 2013