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), Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of a computational complexity, RAIRO, 41, 1, p. 1-18. http://dx.doi.org/10.1051/ro:20070012
TypeArticle accepté pour publication ou publié
MetadataShow full item record
Abstract (EN)We study a deterministic problem of evaluating the worst case performance of ﬂexible solutions in the single machine scheduling. A ﬂexible solution is a set of schedules following a given structure de- termined by a partial order of jobs and a type of the schedules. In this paper, the schedules of active and non-delay type are considered. A ﬂexible solution can be used on-line to absorb the impact of data disturbances related to, for example, job arrival, tool availability or machine breakdowns. The performance of a ﬂexible solution includes the best case and the worst case performances. The best case perfor- mance is an ideal performance that can be achieved only if the on-line conditions allow to implement the best schedule of the set of schedules characterizing the ﬂexible solution. In contrast, the worst case perfor- mance indicates how poorly the ﬂexible solution may perform when fol- lowing the given structure in the on-line circumstances. The best-case and the worst-case performances are usually evaluated by the minimum and maximum values of the considered objective function, respectively. We present algorithmic and computational complexity results for some maximization scheduling problems. In these problems, the jobs to be scheduled have diﬀerent release dates and precedence constraints may be given on the set of jobs.
Subjects / KeywordsScheduling; single machine; maxi- mization problems
Showing items related by title and author.