Minimizing setups for cycle-free ordered sets

Duffus, D.; Rival, I.; Winkler, P.

doi:10.1090/S0002-9939-1982-0660592-3

Minimizing setups for cycle-free ordered sets
HTML articles powered by AMS MathViewer

by D. Duffus, I. Rival and P. Winkler PDF

Proc. Amer. Math. Soc. 85 (1982), 509-513 Request permission

Abstract:

A machine performs a set of jobs one at a time subject to a set of precedence constraints. We consider the problem of scheduling the jobs to minimize the number of "setups".

References

G. Chaty, M. Chein, P. Martin, and G. Petolla, Some results about the number of jumps in acircuit digraphs, Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974), Congressus Numerantium, No. X, Utilitas Math., Winnipeg, Man., 1974, pp. 267–279. MR 0360338
Michel Chein and Pierre Martin, Sur le nombre de sauts d’une forêt, C. R. Acad. Sci. Paris Sér. A-B 275 (1972), A159–A161 (French). MR 302489
M. Chein and M. Habib, The jump number of dags and posets: an introduction, Ann. Discrete Math. 9 (1980), 189–194. MR 597371, DOI 10.1017/s0001867800043305
O. Cogis and M. Habib, Nombre de sauts et graphes série-parallèles, RAIRO Inform. Théor. 13 (1979), no. 1, 3–18, ii (French, with English summary). MR 525454, DOI 10.1051/ita/1979130100031
R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161–166. MR 32578, DOI 10.2307/1969503

Recherche d’un ordre total minimal compatible avec un ordre partial donné

On minimizing setups in precedence constrained scheduling