Maximization of single machine scheduling
Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.; Portmann, Marie-Claude (2004), Maximization of single machine scheduling, Annals of operations research, 129, 1-4, p. 21-32. http://dx.doi.org/10.1023/B:ANOR.0000030679.25466.02
Type
Article accepté pour publication ou publiéDate
2004Journal name
Annals of operations researchVolume
129Number
1-4Publisher
Springer
Pages
21-32
Publication identifier
Metadata
Show full item recordAbstract (EN)
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+n 2) 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.Subjects / Keywords
precedence constraints; release times; maximization problem; semi-active schedules; schedulingRelated items
Showing items related by title and author.
-
Portmann, Marie-Claude; Kovalyov, Mikhail Y.; Aloulou, Mohamed Ali (2007) Article accepté pour publication ou publié
-
Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.; Portmann, Marie-Claude (2003) Communication / Conférence
-
Aissi, Hassene; Aloulou, Mohamed Ali; Kovalyov, Mikhail Y. (2011) Article accepté pour publication ou publié
-
Aloulou, Mohamed Ali; Portmann, Marie-Claude (2005) Chapitre d'ouvrage
-
Aloulou, Mohamed Ali; Portmann, Marie-Claude (2008) Chapitre d'ouvrage