Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity

Mohamed Ali Aloulou; Mikhail Y. Kovalyov; Marie-Claude Portmann

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 1, page 1-18
  • ISSN: 0399-0559

Abstract

top
We study a deterministic problem of evaluating the worst case performance of flexible solutions in the single machine scheduling. A flexible solution is a set of schedules following a given structure determined 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 flexible 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 flexible solution includes the best case and the worst case performances. The best case performance 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 flexible solution. In contrast, the worst case performance indicates how poorly the flexible solution may perform when following 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 different release dates and precedence constraints may be given on the set of jobs.

How to cite

top

Aloulou, Mohamed Ali, Kovalyov, Mikhail Y., and Portmann, Marie-Claude. "Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity ." RAIRO - Operations Research 41.1 (2007): 1-18. <http://eudml.org/doc/250110>.

@article{Aloulou2007,
abstract = { We study a deterministic problem of evaluating the worst case performance of flexible solutions in the single machine scheduling. A flexible solution is a set of schedules following a given structure determined 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 flexible 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 flexible solution includes the best case and the worst case performances. The best case performance 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 flexible solution. In contrast, the worst case performance indicates how poorly the flexible solution may perform when following 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 different release dates and precedence constraints may be given on the set of jobs. },
author = {Aloulou, Mohamed Ali, Kovalyov, Mikhail Y., Portmann, Marie-Claude},
journal = {RAIRO - Operations Research},
keywords = {Scheduling; single machine; schedule flexibility; maximization problems; active and non-delay schedules.},
language = {eng},
month = {6},
number = {1},
pages = {1-18},
publisher = {EDP Sciences},
title = {Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity },
url = {http://eudml.org/doc/250110},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Aloulou, Mohamed Ali
AU - Kovalyov, Mikhail Y.
AU - Portmann, Marie-Claude
TI - Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity
JO - RAIRO - Operations Research
DA - 2007/6//
PB - EDP Sciences
VL - 41
IS - 1
SP - 1
EP - 18
AB - We study a deterministic problem of evaluating the worst case performance of flexible solutions in the single machine scheduling. A flexible solution is a set of schedules following a given structure determined 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 flexible 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 flexible solution includes the best case and the worst case performances. The best case performance 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 flexible solution. In contrast, the worst case performance indicates how poorly the flexible solution may perform when following 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 different release dates and precedence constraints may be given on the set of jobs.
LA - eng
KW - Scheduling; single machine; schedule flexibility; maximization problems; active and non-delay schedules.
UR - http://eudml.org/doc/250110
ER -

References

top
  1. M.A. Aloulou, On the reactive scheduling design using flexible predictive schedules, in Proceedings of IEEE SMC'2002, 6 pages in CD–ROM, Hammamet, October 2002.  
  2. M.A. Aloulou, M.Y. Kovalyov and M.C. Portmann, Maximization problems in single machine scheduling. Ann. Oper. Res.129 (2004) 21–35.  
  3. M.A. Aloulou and M.C. Portmann, An efficient proactive reactive approach to hedge against shop flow disruptions, in Multidisciplinary Scheduling: Thoery and Applications, edited by G. Kendall, E. Burke, S. Petrovic and M. Gendreau, Springer (2005) 223–246.  
  4. C. Artigues, J.-C. Billaut and C. Esswein, Maximization of solution flexibility for robust shop scheduling. Eur. J. Oper. Res.165 (2005) 314–328.  
  5. C. Artigues, F. Roubellat and J.-C. Billaut, Characterization of a set of schedules in a resource constrained multi-project scheduling problem with multiple modes. Inter. J. Industrial Eng. Applications Practice6 (1999) 112–122.  
  6. K.R. Baker, Introduction to sequencing and scheduling. John Wiley and Sons (1974).  
  7. P. Brucker, Scheduling algorithms. Springer-Verlag (1998).  
  8. P. Brucker and S. Knust, Complexity results for scheduling problems. (2003).  URIhttp://www.mathematik.uni-osnabrueck.de/research/OR/class/
  9. R.L. Daniels and P. Kouvelis, Robust scheduling to hedge against processing time uncertainty in single stage production. Manage. Sci.41 (1995) 363–376.  
  10. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, edited by W.H. Freeman (1979).  
  11. R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic machine scheduling: a survey. Ann. Discrete Math.5 (1979) 287–326.  
  12. W. Herroelen and R. Leus, Project scheduling under uncertainty: survey and research potentials. Eur. J. Oper. Res.165 (2005) 289–306.  
  13. E.L. Lawler, Scheduling a single machine to minimize the number of late jobs. Technical report, Computer Science Division, University of California, Berkeley, USA (1983).  
  14. S.V. Mehta and R. Uzsoy, Predictable scheduling of a single machine subject to breakdowns. Inter. J. Compu. Integrated Manufacturing12 (1999) 15–38.  
  15. M.E. Posner, Reducibility among weighted completion time scheduling problems. Ann. Oper. Res. (1990) 91–101.  
  16. W.E. Smith, Various optimizers for single-stage production. Naval Research Logistics Quarterly3 (1956) 59–66.  
  17. V.S. Tanaev, V.S. Gordon and Y.M. Shafransky, Scheduling Theory. Single-Stage Systems. Kluwer Academic Publishers (1994).  
  18. S.D. Wu, E.S. Byeon and R.H. Storer, A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness. Oper. Res.47 (1999) 113–124.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.