TITLE

Maximization Problems in Single Machine Scheduling

AUTHOR(S)
Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.; Portmann, Marie-Claude
PUB. DATE
July 2004
SOURCE
Annals of Operations Research;Jul2004, Vol. 129 Issue 1-4, p21
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
Problems of scheduling n jobs on a single machine to maximize regular objective functions are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Schedules of interest are only those for which the jobs cannot be shifted to start earlier without changing job sequence or violating release times or precedence constraints. Solutions to the maximization problems provide an information about how poorly such schedules can perform. The most general problem of maximizing maximum cost is shown to be reducible to n similar problems of scheduling n−1 jobs available at the same time. It is solved in O( mn+ n2) time, where m is the number of arcs in the precedence graph. When all release times are equal to zero, the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization counterpart with precedence constraints reversed with respect to the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n−1 jobs available at the same time.
ACCESSION #
18724134

 

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics