Algorithms for some maximization scheduling problems on a single machine

Algorithms for some maximization scheduling problems on a single machine

0.00 Avg rating0 Votes
Article ID: iaor20107553
Volume: 71
Issue: 10
Start Page Number: 2070
End Page Number: 2084
Publication Date: Oct 2010
Journal: Automation and Remote Control
Authors: , ,
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-ΣTj and for the problem of maximizing the number of tardy jobs 1‖maxΣUj. 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 j is polynomially solvable. For several special cases of problem 1‖maxΣ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.

Reviews

Required fields are marked *. Your email address will not be published.