Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results

Jean Damay; Alain Quilliot; Eric Sanlaville

RAIRO - Operations Research (2008)

  • Volume: 42, Issue: 3, page 325-359
  • ISSN: 0399-0559

Abstract

top

We deal here with a scheduling problem GPPCSP (Generalized Parallelism and Preemption Constrained Scheduling Problem) which is an extension of both the well-known Resource Constrained Scheduling Problem and the Scheduling Problem with Disjunctive Constraints. We first propose a reformulation of GPPCSP: according to it, solving GPPCSP means finding a vertex of the Feasible Vertex Subset of an Antichain Polyhedron. Next, we state several theoretical results related to this reformulation process and to structural properties of this specific Feasible Vertex Subset (connectivity, ...). We end by focusing on the preemptive case of GPPCSP and by identifying specific instances of GPPCSP which are such that any vertex of the related Antichain Polyhedron may be projected on its related Feasible Vertex Subset without any deterioration of the makespan. For such an instance, the GPPCSP problem may be solved in a simple way through linear programming.

How to cite

top

Damay, Jean, Quilliot, Alain, and Sanlaville, Eric. "Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results." RAIRO - Operations Research 42.3 (2008): 325-359. <http://eudml.org/doc/250432>.

@article{Damay2008,
abstract = {
We deal here with a scheduling problem GPPCSP (Generalized Parallelism and Preemption Constrained Scheduling Problem) which is an extension of both the well-known Resource Constrained Scheduling Problem and the Scheduling Problem with Disjunctive Constraints. We first propose a reformulation of GPPCSP: according to it, solving GPPCSP means finding a vertex of the Feasible Vertex Subset of an Antichain Polyhedron. Next, we state several theoretical results related to this reformulation process and to structural properties of this specific Feasible Vertex Subset (connectivity, ...). We end by focusing on the preemptive case of GPPCSP and by identifying specific instances of GPPCSP which are such that any vertex of the related Antichain Polyhedron may be projected on its related Feasible Vertex Subset without any deterioration of the makespan. For such an instance, the GPPCSP problem may be solved in a simple way through linear programming. },
author = {Damay, Jean, Quilliot, Alain, Sanlaville, Eric},
journal = {RAIRO - Operations Research},
keywords = {Partially ordered sets; hypergraphs; linear programming; polyhedra; multiprocessor scheduling; resource constrained project scheduling problem.; partially ordered sets; resource constrained project scheduling problem},
language = {eng},
month = {8},
number = {3},
pages = {325-359},
publisher = {EDP Sciences},
title = {Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results},
url = {http://eudml.org/doc/250432},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Damay, Jean
AU - Quilliot, Alain
AU - Sanlaville, Eric
TI - Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results
JO - RAIRO - Operations Research
DA - 2008/8//
PB - EDP Sciences
VL - 42
IS - 3
SP - 325
EP - 359
AB - 
We deal here with a scheduling problem GPPCSP (Generalized Parallelism and Preemption Constrained Scheduling Problem) which is an extension of both the well-known Resource Constrained Scheduling Problem and the Scheduling Problem with Disjunctive Constraints. We first propose a reformulation of GPPCSP: according to it, solving GPPCSP means finding a vertex of the Feasible Vertex Subset of an Antichain Polyhedron. Next, we state several theoretical results related to this reformulation process and to structural properties of this specific Feasible Vertex Subset (connectivity, ...). We end by focusing on the preemptive case of GPPCSP and by identifying specific instances of GPPCSP which are such that any vertex of the related Antichain Polyhedron may be projected on its related Feasible Vertex Subset without any deterioration of the makespan. For such an instance, the GPPCSP problem may be solved in a simple way through linear programming.
LA - eng
KW - Partially ordered sets; hypergraphs; linear programming; polyhedra; multiprocessor scheduling; resource constrained project scheduling problem.; partially ordered sets; resource constrained project scheduling problem
UR - http://eudml.org/doc/250432
ER -

References

top
  1. J.F. Allen, Towards a general theory of action and time Art. Intel.23 (1984) 123–154.  Zbl0567.68025
  2. C. Artigues and F. Roubellat, A polynomial activity insertion algorithm in a multiresource schedule with cumulative constraints and multiple nodes. EJOR127-2 (2000) 297–316.  Zbl0990.90034
  3. C. Artigues, P. Michelon and S. Reusser, Insertion techniques for static and dynamic resource constrained project scheduling. EJOR149 (2003) 249–267.  Zbl1040.90013
  4. K. R.Baker, Introduction to Sequencing and Scheduling. Wiley, NY (1974).  
  5. P. Baptiste, Resource constraints for preemptive and non preemptive scheduling. MSC Thesis, University Paris VI (1995).  
  6. P. Baptiste, Demassey, Tight LP bounds for resource constrained project scheduling. OR Spectrum26 (2004) 11.  Zbl1072.90012
  7. S. Benzer, On the topology of the genetic fine structure Proc. Acad. Sci. USA45 (1959) 1607–1620.  
  8. C. Berge, Graphes et Hypergraphes. Dunod Ed., Paris (1975).  
  9. J. Blazewiecz, K.H. Ecker, G. Schmlidt and J. Weglarcz, Scheduling in computer and manufacturing systems. 2th edn, Springer-Verlag, Berlin (1993).  
  10. K.S. Booth and J.S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J. Comp. Sci.13 (1976) 335–379.  Zbl0367.68034
  11. P. Brucker and S. Knust, A linear programming and constraint propoagation based lower bound for the RCPSP. EJOR127 (2000) 355–362.  Zbl0990.90055
  12. P. Brucker, S. Knust, A. Schoo and O. Thiele, A branch and bound algorithm for the resource constrained project scheduling problem. EJOR107 (1998) 272–288.  Zbl0970.90030
  13. J. Carlier and P. Chretienne, Problèmes d'ordonnancements : modélisation, complexité et algorithmes. Masson Ed., Paris (1988).  
  14. M. Carter, A survey on practical applications of examination timetabling algorithms. Oper. Res.34 (1986) 193–202.  
  15. M. Chein and M. Habib, The jump number of Dags and posets. Ann. Discrete Math.9 (1980) 189–194.  Zbl0445.05048
  16. E. Demeulemeester and W. Herroelen, New benchmark results for the multiple RCPSP. Manage. Sci.43 (1997) 1485–1492.  Zbl0914.90160
  17. J. Damay, Techniques de resolution basées sur la programmation linéaire pour l'ordonnancement de projet. Ph.D. Thesis, Université de Clermont-Ferrand, (2005).  
  18. J. Damay, A. Quilliot and E. Sanlaville, Linear programming based algorithms for preemptive and non preemptive RCPSP. EJOR182 (2007) 1012–1022.  Zbl1121.90055
  19. K. Djellab, Scheduling preemptive jobs with precedence constraints on parallel machines. EJOR117 (1999) 355–367.  Zbl0998.90033
  20. D. Dolev and M.K. Warmuth, Scheduling DAGs of bounded heights. J. Algor.5 (1984) 48–59.  Zbl0547.68037
  21. P. Duchet, Problèmes de représentations et noyaux. Thèse d'Etat Paris VI (1981).  
  22. B. Dushnik and W. Miller, Partially ordered sets. Amer. J. Math.63 (1941) 600–610.  Zbl0025.31002
  23. D.R. Fulkerson and J.R. Gross, Incidence matrices and interval graphs. Pac. J. Math.15 (1965) 835–855.  Zbl0132.21001
  24. S.P. Ghosh, File organization: the consecutive retrieval property. Comm. ACM9 (1975) 802–808.  Zbl0246.68004
  25. R.L. Grahamson, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnoy-Khan, Optimization and approximation in deterministic scheduling: a survey. Ann. Discrete Math.5 (1979) 287–326.  
  26. J. Josefowska, M. Mika, R. Rozycki, G. Waligora and J. Weglarcz, An almost optimal heuristic for preemptive Cmax scheduling of dependant task on parallel identical machines. Annals Oper. Res.129 (2004) 205–216.  
  27. W. Herroelen, E. Demeulemeester and B. de Reyck, A classification scheme for project scheduling, in Project Scheduling: recent models, algorithms and applications. Kluwer Acad Publ. (1999) 1–26.  
  28. D.G. Kindall, Incidence matrices, interval graphs and seriation in archaeology, Pac. J. Math. 28 (1969) 565–570.  Zbl0185.03301
  29. R. Kolisch, A. Sprecher and A. Drexel, Characterization and generation of a general class of resource constrained project scheduling problems, Manage. Sci. 41, (10), (1995) 1693–1703.  Zbl0870.90070
  30. L.T. Kou, Polynomial complete consecutive information retrieval problems. SIAM J. Comput.6 (1992) 67–75.  Zbl0354.68036
  31. E.L. Lawler, K.J. Lenstra, A.H.G. Rinnoy-Kan and D.B. Schmoys, Sequencing and scheduling: algorithms and complexity, in Handbook of Operation Research and Management Sciences, Vol 4: Logistics of Production and Inventory, edited by S.C. Graves, A.H.G. Rinnoy-Kan and P.H. Zipkin, North-Holland, (1993) 445–522.  
  32. F. Luccio and F. Preparata, Storage for consecutive retrieval. Inform. Processing Lett.5 (1976) 68–71.  Zbl0354.68034
  33. A. Mingozzi, V. Maniezzo, S. Ricciardelli and L. Bianco, An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation. Manage. Sci.44 (1998) 714–729.  Zbl1004.90036
  34. R.H. Mohring and F.J. Rademacher, Scheduling problems with resource duration interactions. Methods Oper. Res.48 (1984) 423–452.  Zbl0561.90048
  35. A. Moukrim and A. Quilliot, Optimal preemptive scheduling on a fixed number of identical parallel machines. Oper. Res. Lett.33 (2005) 143–151.  Zbl1099.90022
  36. A. Moukrim and A. Quilliot, A relation between multiprocessor scheduling and linear programming. Order14 (1997) 269–278.  Zbl0912.90178
  37. R.R. Muntz and E.G. Coffman, Preemptive scheduling of real time tasks on multiprocessor systems. J.A.C.M.17 (1970) 324–338.  Zbl0216.49702
  38. C.H. Papadimitriou and M. Yannanakis, Scheduling interval ordered tasks. SIAM J. Comput.8 (1979) 405–409.  Zbl0421.68040
  39. J.H. Patterson, A comparizon of exact approaches for solving the multiple constrained resource project scheduling problem. Manage. Sci.30 (1984) 854–867.  
  40. A. Quilliot and S. Xiao, Algorithmic characterization of interval ordered hypergraphs and applications. Discrete Appl. Math.51 (1994) 159–173.  Zbl0810.68105
  41. N. Sauer and M.G. Stone, Rational preemptive scheduling. Order4 (1987) 195–206.  
  42. N. Sauer and M.G. Stone, Preemptive scheduling of interval orders is polynomial. Order5 (1989) 345–348.  Zbl0699.68049
  43. A. Schrijver, Theory of Linear and Integer Programming. Wiley, NY (1986).  Zbl0665.90063
  44. P. Van Hentenryk, Constraint Programming. North Holland (1997).  

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.