Preemptive scheduling and antichain polyhedra. (English) Zbl 1155.90356
Summary: We present a theoretical framework, which is based upon notions of ordered hypergraphs and antichain polyhedra, and which is dedicated to the combinatorial analysis of preemptive scheduling problems submitted to parallelization constraints.This framework allows us to characterize specific partially ordered structures which are such that induced preemptive scheduling problems may be solved through linear programming. To prove that, in the general case, optimal preemptive schedules may be searched inside some connected subset of the vertex set of an Antichain Polyhedron.
MSC:
| 90B22 | Queues and service in operations research |
| 90C27 | Combinatorial optimization |
| 90C05 | Linear programming |
| 05C65 | Hypergraphs |
References:
| [1] | Allen, J. F., Towards a general theory of action and time, Artificial Intelligence, 23, 123-154 (1984) · Zbl 0567.68025 |
| [2] | Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley N.Y |
| [3] | P. Baptiste, Resource constraints for preemptive and non-preemptive scheduling, MSC Thesis, University PARIS VI, 1995; P. Baptiste, Resource constraints for preemptive and non-preemptive scheduling, MSC Thesis, University PARIS VI, 1995 |
| [4] | Benzer, S., On the topology of the genetic fine structure, Proc. Acad. Sci. USA, 45, 1607-1620 (1959) |
| [5] | Berge, C., Graphes et Hypergraphes (1975), Dunod · Zbl 0213.25702 |
| [6] | Blazewiecz, J.; Ecker, K. H.; Schmidt, G.; Weglarz, J., Scheduling in Computer and Manufacturing Systems (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0767.90033 |
| [7] | Booth, K. S.; Lueker, J. S., Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. Comput. Sci., 13, 335-379 (1976) · Zbl 0367.68034 |
| [8] | Brucker, P.; Knust, S., A linear programming and constraint propagation based lower bound for the RCPSP, European J. Oper. Res., 127, 355-362 (2000) · Zbl 0990.90055 |
| [9] | Brucker, P.; Knust, S.; Schoo, A.; Thiele, O., A branch and bound algorithm for the resource constrained project scheduling problem, European J. Oper. Res., 107, 2, 272-288 (1998) · Zbl 0970.90030 |
| [10] | J. Carlier, P. Chretienne, Problèmes d’ordonnancements: Modélisation, complexité et algorithmes, Masson, Paris, 1988; J. Carlier, P. Chretienne, Problèmes d’ordonnancements: Modélisation, complexité et algorithmes, Masson, Paris, 1988 |
| [11] | Carter, M., A survey on practical applications of examination timetabling algorithms, Oper. Res., 34, 2, 193-202 (1986) |
| [12] | Chein, M.; Habib, M., The jump number of Dags and posets: An introduction, Ann. Discrete Math., 9, 189-194 (1980) · Zbl 0445.05048 |
| [13] | Demeulemeester, E.; Herroelen, W., New benchmark results for the multiple resource constrained project scheduling problem, Manage. Sci., 43, 1485-1492 (1997) · Zbl 0914.90160 |
| [14] | Dolev, D.; Warmuth, M. K., Scheduling precedence graphs of bounded heights, J. Algorithms, 5, 48-59 (1984) · Zbl 0547.68037 |
| [15] | Dolev, D.; Warmuth, M. K., Profile scheduling of opposing forests and level orders, SIAM J. Algorithms Discrete Methods, 6, 665-687 (1985) · Zbl 0577.90038 |
| [16] | P. Duchet, Problèmes de représentations et noyaux, Thèse d’Etat PARIS VI, 1981; P. Duchet, Problèmes de représentations et noyaux, Thèse d’Etat PARIS VI, 1981 |
| [17] | Dushnik, B.; Miller, W., Partially ordered sets, Amer. J. Math., 63, 600-610 (1941) · JFM 67.0157.01 |
| [18] | Fulkerson, D. R.; Gross, J. R., Incidence matrices and interval graphs, Pacific J. Math., 15, 835-855 (1965) · Zbl 0132.21001 |
| [19] | Ghosh, S. P., File organization: The consecutive retrieval property, Comm. ACM, 9, 802-808 (1975) · Zbl 0246.68004 |
| [20] | Grahamson, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy-Kan, A. H.G, Optimization and approximation in deterministic sequencing...: A survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044 |
| [21] | Herroelen, W.; Demeulemeester, E.; de Reyck, Bert, A classification scheme for project scheduling, (Project Scheduling: Recent Models, Algorithms and Applications (1999), Kluwer Acad Publishers), 1-26 |
| [22] | Kindall, D. G., Incidence matrices, interval graphs and seriation in archeology, Pacific J. Math., 28, 565-570 (1969) · Zbl 0185.03301 |
| [23] | Kolisch, R.; Sprecher, A.; Drexel, A., Characterization and generation of a general class of resource constrained project scheduling problems, Manage. Sci., 41, 10, 1693-1703 (1995) · Zbl 0870.90070 |
| [24] | Kou, L. T., Polynomial complete consecutive information retrieval problems, SIAM J. Comput., 6, 67-75 (1992) · Zbl 0354.68036 |
| [25] | Lawler, E. L.; Lenstra, K. J.; Rinnoy-Kan, A. H.G.; Schmoys, D. B., Sequencing and scheduling: Algorithms and complexity, (Graves, S. C.; Rinnoy-Kan, A. H.G.; Zipkin, P. H., Handbook of Operation Research and Management Sciences, Vol. 4: Logistics of Production and Inventory (1993), North-Holland: North-Holland Amsterdam), 445-522 · Zbl 0798.90028 |
| [26] | Luccio, F.; Preparata, F. P., Storage for consecutive retrieval, Inform. Process. Lett., 5, 3, 68-71 (1976) · Zbl 0354.68034 |
| [27] | Mingozzi, A.; Maniezzo, V.; Ricciardelli, S.; Bianco, L., An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation, Manage. Sci., 44, 714-729 (1998) · Zbl 1004.90036 |
| [28] | Mohring, R. H.; Rademacher, F. J., Scheduling problems with resource duration interactions, Methods Oper. Res., 48, 423-452 (1984) · Zbl 0561.90048 |
| [29] | Moukrim, A.; Quilliot, A., A relation between multiprocessor scheduling and linear programming, Order, 14, 269-278 (1998) · Zbl 0912.90178 |
| [30] | Moukrim, A.; Quilliot, A., Optimal preemptive scheduling on a fixed number of identical parallel machines, Oper. Res. Lett., 33, 2, 143-150 (2005) · Zbl 1099.90022 |
| [31] | Muntz, R. R.; Coffman, E. G., Preemptive scheduling of real time tasks on multiprocessor systems, J. ACM, 17, 2, 324-338 (1970) · Zbl 0216.49702 |
| [32] | Papadimitriou, C. H.; Yannanakis, M., Scheduling interval ordered tasks, SIAM J. Comput., 8, 405-409 (1979) · Zbl 0421.68040 |
| [33] | Patterson, J. H., A comparison of exact approaches for solving the multiple constrained resource project scheduling problem, Manage. Sci., 30, 7, 854-867 (1984) |
| [34] | Quilliot, A.; Xiao, Sun, Algorithmic characterization of interval ordered hypergraphs and applications, Discrete Appl. Math., 51, 159-173 (1994) · Zbl 0810.68105 |
| [35] | Sauer, N.; Stone, M. G., Rational preemptive scheduling, Order, 4, 195-206 (1987) · Zbl 0648.68044 |
| [36] | Sauer, N.; Stone, M. G., Preemptive scheduling of interval orders is polynomial, Order, 5, 345-348 (1989) · Zbl 0699.68049 |
| [37] | Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley Inter: Wiley Inter NY · Zbl 0665.90063 |
| [38] | Van Hentenryk, P., Constraint Programming (1997), North Holland |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
