Satisfying due-dates in the presence of sequence dependent family setups with a special comedown structure

Creative Commons License

Taner M. R., Hodgson T. J., King R. E., Schultz S. R.

COMPUTERS & INDUSTRIAL ENGINEERING, vol.52, no.1, pp.57-70, 2007 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 52 Issue: 1
  • Publication Date: 2007
  • Doi Number: 10.1016/j.cie.2006.10.008
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.57-70
  • Keywords: scheduling, maximum lateness, sequence dependent family setups, comedown, heuristics, MINIMIZE MAXIMUM LATENESS, APPROXIMATION ALGORITHMS, DELIVERY TIMES, JOB FAMILIES, UP TIMES, BATCH
  • TED University Affiliated: No


This paper addresses a static, n-job, single-machine scheduling problem with sequence dependent family setups. The setup matrix follows a special structure where a constant setup is required only if a job from a smaller indexed family is an immediate successor of one from a larger indexed family. The objective is to minimize the maximum lateness (L.,x). A two-step neighborhood search procedure and an implicit enumeration scheme are proposed. Both procedures exploit the problem structure. The enumeration scheme produces optimum solutions to small and medium sized problems in reasonable computational times, yet it fails to perform efficiently in larger instances. Computational results show that the heuristic procedure is highly effective, and is efficient even for extremely large problems. (c) 2006 Elsevier Ltd. All rights reserved.