Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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 Free Access

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 (50 #12788)
  • [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 (46 #1633)
  • [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 (81m:05071)
  • [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 (81h:05068)
  • [5] R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 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

DOI: http://dx.doi.org/10.1090/S0002-9939-1982-0660592-3
PII: S 0002-9939(1982)0660592-3
Article copyright: © Copyright 1982 American Mathematical Society