|
Avtomatika i Telemekhanika, 2010, Issue 10, Pages 63–79
(Mi at894)
|
|
|
|
This article is cited in 5 scientific papers (total in 5 papers)
Scheduling Problems on a Single Machine
Algorithms for some maximization scheduling problems on a single machine
E. R. Gafarova, A. A. Lazareva, F. Wernerb a Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia
b Otto-von-Guericke-Universität Magdeburg, Magdeburg, Germany
Abstract:
In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness $1\|\max\sum T_j$ and for the problem of maximizing the number of tardy jobs $1\|\max\sum U_j$. In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem $1\|\max\sum U_j$ is polynomially solvable. For several special cases of problem $1\|\max\sum T_j$, we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.
Citation:
E. R. Gafarov, A. A. Lazarev, F. Werner, “Algorithms for some maximization scheduling problems on a single machine”, Avtomat. i Telemekh., 2010, no. 10, 63–79; Autom. Remote Control, 71:10 (2010), 2070–2084
Linking options:
https://www.mathnet.ru/eng/at894 https://www.mathnet.ru/eng/at/y2010/i10/p63
|
Statistics & downloads: |
Abstract page: | 525 | Full-text PDF : | 137 | References: | 59 | First page: | 7 |
|