×

zbMATH — the first resource for mathematics

Multiprocessor scheduling under precedence constraints: polyhedral results. (English) Zbl 1120.90070
Summary: We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented.

MSC:
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C35 Programming involving graphs or networks
Software:
ABACUS; CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bertsekas, D.P.; Tsitsiklis, J.N., Parallel and distributed computation—numerical methods, (1989), Prentice-Hall Englewood Cliffs, NJ · Zbl 0743.65107
[2] Blazewicz, J.; Cellary, W.; Slowinski, R.; Weglarz, J., Scheduling under resource constraints—deterministic models, (1986), J.C. Baltzer AG Basel
[3] T. Christof, G. Reinelt, Low-dimensional linear ordering polytopes, Technical Report, Universität Heidelberg, 1997.
[4] Coffman, E.G.; Denning, P.J., Operating systems theory, (1973), Prentice-Hall Englewood Cliffs, NJ
[5] Coll, P.E., A polyhedral approach to scheduling unrelated processors under precedence constrains, doctorate dissertation, (2002), University of Buenos Aires Argentina
[6] Cook, W.J.; Cunnigham, W.H.; Pulleyblank, W.R.; Schrijver, A., Combinatorial optimization, (1998), Wiley New York
[7] Doignon, J.P.; Fiorini, Samuel, Facets of the weak order polytope derived from the induced partition projection, SIAM J. discrete math., 15, 1, 112-121, (2002) · Zbl 1009.52024
[8] Garey, M.R.; Johnson, D.S., Strong NP-completeness results: motivation, examples and implications, J. ACM, 25, 499-508, (1978) · Zbl 0379.68035
[9] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company San Francisco · Zbl 0411.68039
[10] Grötschel, M.; Jünger, M.; Reinelt, G., A cutting plane algorithm for the linear ordering problem, Oper. res., 32, 1195-1220, (1984) · Zbl 0554.90077
[11] Grötschel, M.; Jünger, M.; Reinelt, G., Facets of the linear ordering polytope, Math. program., 33, 43-60, (1985) · Zbl 0577.05035
[12] Grötschel, M.; Jünger, M.; Reinelt, G., On the acyclic subgraph polytope, Math. program., 33, 28-42, (1985) · Zbl 0577.05034
[13] Grötschel, M.; Wakabayashi, Y., A cutting plane algorithm for a clustering problem, Math. program. ser. B, 45, 59-96, (1989) · Zbl 0675.90072
[14] Grötschel, M.; Wakabayashi, Y., Facets of the clique partitioning polytope, Math. program., 47, 367-387, (1990) · Zbl 0715.90092
[15] M.A.M.C. Gurgel, Poliedros de grafos transitivos, Ph.D. Thesis, Department of Computing Science, University of São Paulo, 1992.
[16] Gurgel, M.A.M.C.; Wakabayashi, Y., Adjacency of vertices of the complete pre-order polytope, Discrete math., 175, 1-3, 163-172, (1997) · Zbl 0886.05107
[17] Ibarra, O.H.; Sohn, S.M., On mapping systolic algorithms onto the hypercube, IEEE trans. parallel distrib. systems, 1, 48-63, (1990)
[18] ILOG, Inc., Using the CPLEX Callable Library, Version 6.0, 1998.
[19] J.P. Kitajima, Modèles quantitatifs d’algorithmes parallèles, Ph.D. Thesis, Institut National Polytechnique de Grenoble, 1992.
[20] J.P. Kitajima, B. Plateau, P. Bouvry, D. Trystram, A method and a tool for performance evaluation—a case study: evaluating mapping strategies, Technical Report, Institut National Polytechnique de Grenoble, 1996.
[21] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequencing and scheduling: algorithms and complexity, Report NFI 11.89/03, Eindhoven Institute of Technology, Department of Mathematics and Computer Science, Eindhoven, 1989.
[22] Maculan, N.; Porto, S.C.S.; Ribeiro, C.C.; de Souza, C.C., A new formulation for scheduling unrelated processors under precedence constraints, RAIRO rech. opér., 33, 87-90, (1999) · Zbl 0958.90046
[23] Madal, S.; Sinclair, J.B., Performance of synchronous parallel algorithms with regular structures, IEEE trans. parallel distrib. systems, 2, 105-116, (1991)
[24] D.A. Menascé, S.C.S. Porto, Processor assignment in heterogeneous parallel architectures, Proceedings of the IEEE International Parallel Processing Symposium, Beverly Hills, 1992, pp. 186-191.
[25] Müller, R., On the partial order polytope of a digraph, Math. program. ser. A, 73, 31-49, (1996) · Zbl 0848.90105
[26] Porto, S.C.; Kitajima, J.P.; Ribeiro, C.C., Performance evaluation of a parallel tabu search task scheduling algorithm, Parallel comput., 26, 73-90, (2000) · Zbl 1046.68506
[27] Porto, S.C.; Ribeiro, C.C., A tabu search approach to task scheduling on heterogeneous processors under precedence constraints, Internat. J. high speed comput., 7, 45-71, (1995)
[28] Porto, S.C.; Ribeiro, C.C., Parallel tabu search message-passing synchronous strategies for task scheduling under precedence constraints, J. heuristics, 1, 207-223, (1995) · Zbl 0853.68064
[29] A.S. Schulz, Polytopes and scheduling, Ph.D. Thesis, Technischen Universität Berlin, 1996. · Zbl 0859.90088
[30] S. Thienel, ABACUS—A Branch-And-CUt System, Ph.D. Thesis, Universitat zu Köln, 1995.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.