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 circuit digraphs, Proc. Fifth Southeastern Conf. Combinatorics, Graph Theory and Computing, Utilitas Math., Winnipeg, 1974, pp. 267-279. MR 0360338 (50:12788)
  • [2] M. Chein and P. Martin, Sur le nombre de sauts d'une forêt, C. R. Acad. Sci. Paris 275 (1972), 159-161. MR 0302489 (46:1633)
  • [3] M. Chein and H. Habib, The jump number of dags and posets: an introduction, Ann. Discrete Math. 9 (1980), 189-194. MR 597371 (81m:05071)
  • [4] O. Cogis and M. Habib, Nombre de sauts et graphes série-parallèles, RAIRO Inform. Théor. 13 (1979), 3-18. MR 525454 (81h:05068)
  • [5] R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. 51 (1950), 161-166. MR 0032578 (11:309f)
  • [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