Two-machine flowshop scheduling problem to minimize total completion time with bounded setup and processing times


Allahverdi A.

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, no.1, pp.386-400, 2006 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Publication Date: 2006
  • Doi Number: 10.1016/j.ijpe.2005.10.002
  • Journal Name: INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.386-400
  • Keywords: Bounded processing times, Bounded setup times, Dominance relations, Flowshop, Scheduling
  • Gazi University Affiliated: No

Abstract

The two-machine flowshop scheduling problem is addressed where setup times are considered as separate from processing times and where the objective is to minimize total completion time. All setup and processing times on both machines are unknown variables (before the actual occurrence of these times) where the only known information is the lower and upper bounds for both setup and processing times of each job. In such an environment, there may not exist a unique schedule that remains optimal for all possible realizations of setup and processing times, and therefore, a set of dominating schedules (which dominate all other schedules) has to be obtained. The objective in such a scheduling environment is to reduce the size of dominating schedules set. Two dominance relations are developed for the considered problem. Illustrative numerical examples are given and computational experiments on randomly generated problems are conducted. The computational experiments show that the developed dominance relations are quite helpful in reducing the size of dominating schedules. (c) 2006 Elsevier B.V. All rights reserved.