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
TypeArticle accepté pour publication ou publié
Journal nameAnnals of operations research
MetadataShow full item record
Abstract (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 / Keywordsprecedence constraints; release times; maximization problem; semi-active schedules; scheduling
Showing items related by title and author.
Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of a computational complexity Portmann, Marie-Claude; Kovalyov, Mikhail Y.; Aloulou, Mohamed Ali (2007) Article accepté pour publication ou publié