A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs

Chi To Ng, J. B. Wang, Edwin Tai Chiu Cheng, L. L. Liu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

62 Citations (Scopus)

Abstract

In this paper we consider a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job we mean that the job's processing time is an increasing function of its starting time. We model job deterioration as a function that is proportional to a linear function of time. The objective is to find a sequence that minimizes the total completion time of the jobs. For the general case, we derive several dominance properties, some lower bounds, and an initial upper bound by using a heuristic algorithm, and apply them to speed up the elimination process of a branch-and-bound algorithm developed to solve the problem.
Original languageEnglish
Pages (from-to)83-90
Number of pages8
JournalComputers and Operations Research
Volume37
Issue number1
DOIs
Publication statusPublished - 1 Jan 2010

Keywords

  • Branch-and-bound algorithm
  • Deteriorating jobs
  • Flow shop
  • Scheduling
  • Total completion time

ASJC Scopus subject areas

  • Computer Science(all)
  • Management Science and Operations Research
  • Modelling and Simulation

Cite this