Show simple item record

dc.contributor.authorAloulou, Mohamed Ali
dc.contributor.authorKovalyov, Mikhail Y.
dc.contributor.authorPortmann, Marie-Claude
dc.subjectprecedence constraintsen
dc.subjectrelease timesen
dc.subjectmaximization problemen
dc.subjectsemi-active schedulesen
dc.titleMaximization of single machine schedulingen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherFaculty of Economics, Belarus State University;Biélorussie
dc.contributor.editoruniversityotherEcole des Mines de Nancy;France
dc.description.abstractenProblems 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.en
dc.relation.isversionofjnlnameAnnals of operations research
dc.subject.ddclabelRecherche opérationnelleen

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record