Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Minimizing setups for cycle-free ordered sets

Authors: D. Duffus, I. Rival and P. Winkler
Journal: Proc. Amer. Math. Soc. 85 (1982), 509-513
MSC: Primary 06A10
MathSciNet review: 660592
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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), Utilitas Math., Winnipeg, Man., 1974, pp. 267–279. Congressus Numerantium, No. X. MR 0360338
  • [2] 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 0302489
  • [3] M. Chein and M. Habib, The jump number of dags and posets: an introduction, Ann. Discrete Math. 9 (1980), 189–194. Combinatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part II. MR 597371
  • [4] 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,
  • [5] R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161–166. MR 0032578,
  • [6] J. Kuntzmann and A. Verdillon, Recherche d'un ordre total minimal compatible avec un ordre partial donné, Séminaire Institut de Mathématique de Grenoble, 1971.
  • [7] W. R. Pulleyblank, On minimizing setups in precedence constrained scheduling, Discrete Appl. Math, (to appear).

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 06A10

Retrieve articles in all journals with MSC: 06A10

Additional Information

Article copyright: © Copyright 1982 American Mathematical Society

American Mathematical Society