Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T17:30:25.915Z Has data issue: false hasContentIssue false
  • English
  • Français

Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results

Published online by Cambridge University Press:  20 August 2008

Jean Damay ,
Alain Quilliot  and
Eric Sanlaville
Jean Damay
Affiliation:
LIMOS, UMR CNRS 6158, Bât ISIMA, Université Blaise Pascal, Campus des Cézeaux, BP 125, 63173 Aubière, France; [email protected], [email protected], [email protected]
Alain Quilliot
Affiliation:
LIMOS, UMR CNRS 6158, Bât ISIMA, Université Blaise Pascal, Campus des Cézeaux, BP 125, 63173 Aubière, France; [email protected], [email protected], [email protected]
Eric Sanlaville
Affiliation:
LIMOS, UMR CNRS 6158, Bât ISIMA, Université Blaise Pascal, Campus des Cézeaux, BP 125, 63173 Aubière, France; [email protected], [email protected], [email protected]
Get access

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.

Keywords

Partially ordered setshypergraphslinear programmingpolyhedramultiprocessor schedulingresource constrained projectscheduling problem.
Type
Research Article
Information
RAIRO - Operations Research , Volume 42 , Issue 3 , July 2008 , pp. 325 - 359
Copyright
© EDP Sciences, ROADEF, SMAI, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J.F. Allen, Towards a general theory of action and time Art. Intel. 23 (1984) 123–154.
Artigues, C. and Roubellat, F., A polynomial activity insertion algorithm in a multiresource schedule with cumulative constraints and multiple nodes. EJOR 127-2 (2000) 297–316. CrossRef
Artigues, C., Michelon, P. and Reusser, S., Insertion techniques for static and dynamic resource constrained project scheduling. EJOR 149 (2003) 249–267. CrossRef
K. R.Baker, Introduction to Sequencing and Scheduling. Wiley, NY (1974).
P. Baptiste, Resource constraints for preemptive and non preemptive scheduling. MSC Thesis, University Paris VI (1995).
Baptiste, P., Demassey, Tight LP bounds for resource constrained project scheduling. OR Spectrum 26 (2004) 11. CrossRef
S. Benzer, On the topology of the genetic fine structure Proc. Acad. Sci. USA 45 (1959) 1607–1620.
C. Berge, Graphes et Hypergraphes. Dunod Ed., Paris (1975).
J. Blazewiecz, K.H. Ecker, G. Schmlidt and J. Weglarcz, Scheduling in computer and manufacturing systems. 2th edn, Springer-Verlag, Berlin (1993).
Booth, K.S. and Lueker, J.S., Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J. Comp. Sci. 13 (1976) 335–379.
Brucker, P. and Knust, S., A linear programming and constraint propoagation based lower bound for the RCPSP. EJOR 127 (2000) 355–362. CrossRef
Brucker, P., Knust, S., Schoo, A. and Thiele, O., A branch and bound algorithm for the resource constrained project scheduling problem. EJOR 107 (1998) 272–288. CrossRef
J. Carlier and P. Chretienne, Problèmes d'ordonnancements : modélisation, complexité et algorithmes. Masson Ed., Paris (1988).
Carter, M., A survey on practical applications of examination timetabling algorithms. Oper. Res. 34 (1986) 193–202. CrossRef
Chein, M. and Habib, M., The jump number of Dags and posets. Ann. Discrete Math. 9 (1980) 189–194. CrossRef
Demeulemeester, E. and Herroelen, W., New benchmark results for the multiple RCPSP. Manage. Sci. 43 (1997) 1485–1492. CrossRef
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).
Damay, J., Quilliot, A. and Sanlaville, E., Linear programming based algorithms for preemptive and non preemptive RCPSP. EJOR 182 (2007) 1012–1022. CrossRef
Djellab, K., Scheduling preemptive jobs with precedence constraints on parallel machines. EJOR 117 (1999) 355–367. CrossRef
Dolev, D. and Warmuth, M.K., Scheduling DAGs of bounded heights. J. Algor. 5 (1984) 48–59. CrossRef
P. Duchet, Problèmes de représentations et noyaux. Thèse d'Etat Paris VI (1981).
Dushnik, B. and Miller, W., Partially ordered sets. Amer. J. Math. 63 (1941) 600–610. CrossRef
Fulkerson, D.R. and Gross, J.R., Incidence matrices and interval graphs. Pac. J. Math. 15 (1965) 835–855. CrossRef
Ghosh, S.P., File organization: the consecutive retrieval property. Comm. ACM 9 (1975) 802–808.
Grahamson, R.L., Lawler, E.L., Lenstra, J.K. and Rinnoy-Khan, A.H.G., Optimization and approximation in deterministic scheduling: a survey. Ann. Discrete Math. 5 (1979) 287–326. CrossRef
Josefowska, J., Mika, M., Rozycki, R., Waligora, G. and Weglarcz, J., An almost optimal heuristic for preemptive Cmax scheduling of dependant task on parallel identical machines. Annals Oper. Res. 129 (2004) 205–216. CrossRef
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.
D.G. Kindall, Incidence matrices, interval graphs and seriation in archaeology, Pac. J. Math. 28 (1969) 565–570.
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.
Kou, L.T., Polynomial complete consecutive information retrieval problems. SIAM J. Comput. 6 (1992) 67–75. CrossRef
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.
Luccio, F. and Preparata, F., Storage for consecutive retrieval. Inform. Processing Lett. 5 (1976) 68–71. CrossRef
Mingozzi, A., Maniezzo, V., Ricciardelli, S. and Bianco, L., An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation. Manage. Sci. 44 (1998) 714–729. CrossRef
Mohring, R.H. and Rademacher, F.J., Scheduling problems with resource duration interactions. Methods Oper. Res. 48 (1984) 423–452.
Moukrim, A. and Quilliot, A., Optimal preemptive scheduling on a fixed number of identical parallel machines. Oper. Res. Lett. 33 (2005) 143–151. CrossRef
Moukrim, A. and Quilliot, A., A relation between multiprocessor scheduling and linear programming. Order 14 (1997) 269–278. CrossRef
Muntz, R.R. and Coffman, E.G., Preemptive scheduling of real time tasks on multiprocessor systems. J.A.C.M. 17 (1970) 324–338.
Papadimitriou, C.H. and Yannanakis, M., Scheduling interval ordered tasks. SIAM J. Comput. 8 (1979) 405–409. CrossRef
Patterson, J.H., A comparizon of exact approaches for solving the multiple constrained resource project scheduling problem. Manage. Sci. 30 (1984) 854–867. CrossRef
Quilliot, A. and Xiao, S., Algorithmic characterization of interval ordered hypergraphs and applications. Discrete Appl. Math. 51 (1994) 159–173. CrossRef
Sauer, N. and Stone, M.G., Rational preemptive scheduling. Order 4 (1987) 195–206. CrossRef
Sauer, N. and Stone, M.G., Preemptive scheduling of interval orders is polynomial. Order 5 (1989) 345–348. CrossRef
A. Schrijver, Theory of Linear and Integer Programming. Wiley, NY (1986).
P. Van Hentenryk, Constraint Programming. North Holland (1997).