×

An algorithm for minimizing setups in precedence constrained scheduling. (English) Zbl 0584.90041

Consider a set of tasks to be scheduled on a single processor subject to precedence constraints. A setup occurs when a task is performed immediately after another task which is not its predecessor. The general problem is to find a schedule minimizing the number of setups. We present a decomposition approach for this problem. This leads to new complexity results and the identification of new classes of precedence constraints for which the problem is efficiently solvable.

MSC:

90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Buer, H.; Mohring, R., A fast algorithm for the decomposition of graphs and posets, Math. Oper. Res., 8, 170-184 (1983) · Zbl 0517.05057
[2] Chein, M.; Habib, M., The jump number of dags and posets: An introduction, Ann. Discrete Math., 9, 189-194 (1980) · Zbl 0445.05048
[3] Cogis, O.; Habib, M., Nombre de sauts et graphes serie-parallels, RAIRO Inform. Theor., 13, 3-18 (1979) · Zbl 0413.05013
[4] Cunningham, W. H., Decomposition of directed graphs, SIAM J. Algebraic Discrete Methods, 3, 214-228 (1982) · Zbl 0497.05031
[5] Duffus, D.; Rival, I.; Winkler, P., Minimizing setups for cycle-free ordered sets (1981), Emory Unit: Emory Unit Atlanta, GA, Preprint · Zbl 0497.06002
[6] El-Zahar, M. H.; Rival, I., Greedy linear extensions to minimize jumps, (Res. Report No. 551 (1983), The University of Calgary) · Zbl 0569.06001
[7] Faigle, U.; Gierz, G., A construction for strongly greedy ordered sets Proc. 8. Symp. Oper. Res., Karlsruhe (1983), to appear
[8] Faigle, U.; Gierz, G.; Schrader, R., Algorithmic approaches to setup minimization, (Report 83297-OR (1983), University of Bonn) · Zbl 0575.68046
[9] Gierz, G.; Poguntke, W., Minimizing setups for ordered sets: A linear algebraic approach, SIAM J. Algebraic Discrete Methods, 132-144 (1983) · Zbl 0517.06004
[10] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Recent developments in deterministic sequencing and scheduling: A survey, (Report BW 146 (1981), Mathematisch Centrum: Mathematisch Centrum Amsterdam) · Zbl 0482.68035
[11] Lenstra, J. K.; Rinnooy Kan, A. H.G., Scheduling theory since 1981: An annotated bibliography Report BW 188 (1983), Mathematisch Centrum: Mathematisch Centrum Amsterdam · Zbl 0516.68037
[12] Muller, J. H.; Spinrad, J., On-Line Modular Decomposition, (Report GIT-ICS-84/11 (1984), Georgia Inst. of Tech)
[13] Pulleyblank, W. R., On minimizing setups in precedence constrained scheduling, (Report 81105-OR (1981), University of Bonn) · Zbl 0318.65027
[14] Rival, I., Optimal linear extensions by interchanging chains, Proc. Amer. Math. Soc., 89, 387-394 (1983) · Zbl 0523.06003
[15] J. Spinrad, On comparability and permutation graphs, SIAM J. Comput., to appear.; J. Spinrad, On comparability and permutation graphs, SIAM J. Comput., to appear. · Zbl 0568.68051
[16] Steiner, G., Machine scheduling with precedence constraints, (Ph.D. thesis (1982), Dept. of Combinatorics and Optimization, The Univ. of Waterloo) · Zbl 0474.90048
[17] Syslo, M. S., A labeling algorithm to recognize a line digraph and output its root graph, Inform Process. Lett., 15, 28-30 (1982) · Zbl 0483.68062
[18] Valdes, J.; Tarjan, R. E.; Lawler, E. L., The recognition of series-parallel digraphs, SIAM J. Comput., 11, 298-313 (1982) · Zbl 0478.68065
[19] Faigle, U.; Schrader, R., Comparability graphs and order invariants, (Report 83308-OR (1983), University of Bonn)
[20] Habib, M., Comparability invariants, (Pouzet, M.; Richard, D., Ordres: Description et Rôles (1984), North-Holland: North-Holland Amsterdam), 371-386
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.