Сhapter
Single Machine Scheduling With a Non-Renewable Financial Resource
.
Gafarov E., Lazarev A. A., Werner F.
We consider single machine scheduling problems with a non-renewable resource. This type of problems has not been intensively investigated in the literature so far. For several problems of this type 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 results. Particular attention is given to the problem of minimizing total tardiness. In addition, for the so-called budget scheduling problem with minimizing the makespan, we present some properties of feasible schedules.
Lazarev A. A., , in: Optimization and applications (OPTIMA-2009). M.: -, 2009. P. 56–57..
We are given a set $N=\{1,\dots,n\}$ of $n$ jobs that must beprocessed on $m$ machines $M=\{1,\dots,m\}$. Preemption of thejobs is not allowed. Each machine can handle only one job at atime. For each job $j$ we have: $r_j$ -- release date $0\lep_{ji}\le +\infty$ -- processing time job $j$ on the machine $i$(if $p_{ji}=+\infty,$ then job ...
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
Gafarov E., Lazarev A. A., Werner F., /. 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., 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
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
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., Korenev P. S., В кн.: Труды третьей российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения»: труды и пленарные доклады участников конференции УКИ`12. М.: ИПУ РАН, 2012. С. 267–274..
Задачи формирования составов и расписания движения грузовых поездов могут быть сформулированы как задач и теории расписаний. Многие из этих задач являются NP-трудными, в связи с чем возникает проблема поиска приближенного решения таких задач. Предлагается метод, основанный на введении метрики для пространства параметров задачи, позволяющий за полиномиальное время находить решение задачи с гарантированной абсолютной погрешностью целевой ...
Added: December 30, 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., Журнал вычислительной математики и математической физики 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., , in: European Conference on Operational Research - 2010. Lisbon: [б.и.], 2010..
We study the classical NP-hard non-preemptive single machine scheduling problem to minimize the maximum penalty with release dates. Penalty of each job is a monotone and non-decreasing function of its completion time. We propose polynomial algorithms for the dual and inverse problems where the minimum penalty is maximized. Both algorithms run in quadratic time. Note ...
Added: March 4, 2013
Скиндерев С., Lazarev A. A., , in: Workshop on Models and Algorithms for Planning and Scheduling Problems. Стамбул: [б.и.], 2007..
We consider the approach to construct approximation schedule with the guaranteed absolute error for the $NP-$hard scheduling problems minimizing maximum lateness. ...
Added: March 4, 2013
Werner F., Lazarev A. A., Automation and Remote Control 2010 Vol. 71 No. 10 P. 2019–2020.
Foreword to the thematical issue devoted to the seventieth anniversary of Academician V.S. Tanaev ...
Added: November 22, 2012
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
Gafarov E., Lazarev A. A., Werner F., /. 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
Lazarev A. A., Baranov A. V., , in: II International Conference Optimization and Application (OPTIMA-2011). M.: -, 2011. P. 149–152..
Added: March 4, 2013
Lazarev A. A., Kvaratskhelia A., Gafarov E., Доклады Академии наук 2007 Т. 412 № 6 С. 739–742.
27.47.19 Исследование операций
28.15.19 Нелинейные детерминированные системы
28.19.15 Оптимальные системы
28.29.15 Методы исследования операций ...
Added: November 23, 2012
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., 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
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., Baranov A. V., Amsterdam: University of Amsterdam, 2011..
Added: March 4, 2013
Lazarev A. A., Kvaratskhelia A., Доклады Академии наук 2010 Т. 432 № 6 С. 746–749.
Одним из актуальных вопросов разработки математической теории расписаний является построение метрик, которые можно использовать при разработке точных и приближенных алгоритмов решения задач. Введение метрических пространств для $NP$-трудных задач теории расписаний позволяет применять общие математические подходы к нахождению приближенного решения с гарантированной абсолютной погрешностью. Ранее для $NP$-трудных задач с критерием минимизации максимального временн\'ого смещения $\{P,R,Q\}|prec,r_j|\{L_{\max},C_{\max}\}$ была ...
Added: November 22, 2012
Kvaratskhelia A., Lazarev A. A., , in: IFAC Symposium on Information Control Problems in Manufacturing (2009). M.: [б.и.], 2009..
In this paper we consider the minimizing total weightedcompletion time in preemptive equal job length schedulingproblem on a single machine. We propose a polynomialtime algorithm that solves the problem. Before this paper the problem were known to be open. ...
Added: March 4, 2013
Lazarev A. A., , in: Optimization and applications (OPTIMA-2009). M.: -, 2009. P. 56–57..
We are given a set $N=\{1,\dots,n\}$ of $n$ jobs that must beprocessed on $m$ machines $M=\{1,\dots,m\}$. Preemption of thejobs is not allowed. Each machine can handle only one job at atime. For each job $j$ we have: $r_j$ -- release date $0\lep_{ji}\le +\infty$ -- processing time job $j$ on the machine $i$(if $p_{ji}=+\infty,$ then job ...
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
Gafarov E., Lazarev A. A., Werner F., /. 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., 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
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
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., Korenev P. S., В кн.: Труды третьей российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения»: труды и пленарные доклады участников конференции УКИ`12. М.: ИПУ РАН, 2012. С. 267–274..
Задачи формирования составов и расписания движения грузовых поездов могут быть сформулированы как задач и теории расписаний. Многие из этих задач являются NP-трудными, в связи с чем возникает проблема поиска приближенного решения таких задач. Предлагается метод, основанный на введении метрики для пространства параметров задачи, позволяющий за полиномиальное время находить решение задачи с гарантированной абсолютной погрешностью целевой ...
Added: December 30, 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., Журнал вычислительной математики и математической физики 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., , in: European Conference on Operational Research - 2010. Lisbon: [б.и.], 2010..
We study the classical NP-hard non-preemptive single machine scheduling problem to minimize the maximum penalty with release dates. Penalty of each job is a monotone and non-decreasing function of its completion time. We propose polynomial algorithms for the dual and inverse problems where the minimum penalty is maximized. Both algorithms run in quadratic time. Note ...
Added: March 4, 2013
Скиндерев С., Lazarev A. A., , in: Workshop on Models and Algorithms for Planning and Scheduling Problems. Стамбул: [б.и.], 2007..
We consider the approach to construct approximation schedule with the guaranteed absolute error for the $NP-$hard scheduling problems minimizing maximum lateness. ...
Added: March 4, 2013
Werner F., Lazarev A. A., Automation and Remote Control 2010 Vol. 71 No. 10 P. 2019–2020.
Foreword to the thematical issue devoted to the seventieth anniversary of Academician V.S. Tanaev ...
Added: November 22, 2012
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
Gafarov E., Lazarev A. A., Werner F., /. 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
Lazarev A. A., Baranov A. V., , in: II International Conference Optimization and Application (OPTIMA-2011). M.: -, 2011. P. 149–152..
Added: March 4, 2013
Lazarev A. A., Kvaratskhelia A., Gafarov E., Доклады Академии наук 2007 Т. 412 № 6 С. 739–742.
27.47.19 Исследование операций
28.15.19 Нелинейные детерминированные системы
28.19.15 Оптимальные системы
28.29.15 Методы исследования операций ...
Added: November 23, 2012
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., 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
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., Baranov A. V., Amsterdam: University of Amsterdam, 2011..
Added: March 4, 2013
Lazarev A. A., Kvaratskhelia A., Доклады Академии наук 2010 Т. 432 № 6 С. 746–749.
Одним из актуальных вопросов разработки математической теории расписаний является построение метрик, которые можно использовать при разработке точных и приближенных алгоритмов решения задач. Введение метрических пространств для $NP$-трудных задач теории расписаний позволяет применять общие математические подходы к нахождению приближенного решения с гарантированной абсолютной погрешностью. Ранее для $NP$-трудных задач с критерием минимизации максимального временн\'ого смещения $\{P,R,Q\}|prec,r_j|\{L_{\max},C_{\max}\}$ была ...
Added: November 22, 2012
Kvaratskhelia A., Lazarev A. A., , in: IFAC Symposium on Information Control Problems in Manufacturing (2009). M.: [б.и.], 2009..
In this paper we consider the minimizing total weightedcompletion time in preemptive equal job length schedulingproblem on a single machine. We propose a polynomialtime algorithm that solves the problem. Before this paper the problem were known to be open. ...
Added: March 4, 2013