We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Algorithms for some maximization scheduling problems on a single machine.
- Authors
Gafarov, E. R.; Lazarev, A. A.; Werner, F.
- 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-Σ T and for the problem of maximizing the number of tardy jobs 1|maxΣ U. 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-Σ T is polynomially solvable. For several special cases of problem 1|maxΣ T, 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.
- Subjects
SCHEDULING; ALGORITHMS; POLYNOMIALS; MATHEMATICAL optimization; NUMERICAL analysis
- Publication
Automation & Remote Control, 2010, Vol 71, Issue 10, p2070
- ISSN
0005-1179
- Publication type
Article
- DOI
10.1134/S0005117910100061