Bi-criteria minimization for the permutation flowshop scheduling problem with machine-based learning effects

Yu Hsiang Chung*, Lee-Ing Tong

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

In traditional scheduling problems, the processing time for the given job is assumed to be a constant regardless of whether the job is scheduled earlier or later. However, the phenomenon named "learning effect" has extensively been studied recently, in which job processing times decline as workers gain more experience. This paper discusses a bi-criteria scheduling problem in an m-machine permutation flowshop environment with varied learning effects on different machines. The objective of this paper is to minimize the weighted sum of the total completion time and the makespan. A dominance criterion and a lower bound are proposed to accelerate the branch-and-bound algorithm for deriving the optimal solution. In addition, the near-optimal solutions are derived by adapting two well-known heuristic algorithms. The computational experiments reveal that the proposed branch-and-bound algorithm can effectively deal with problems with up to 16 jobs, and the proposed heuristic algorithms can yield accurate near-optimal solutions.

Original languageEnglish
Pages (from-to)302-312
Number of pages11
JournalComputers and Industrial Engineering
Volume63
Issue number1
DOIs
StatePublished - 1 Jan 2012

Keywords

  • Flowshop
  • Learning effect
  • Makespan
  • Scheduling
  • Total completion time

Fingerprint Dive into the research topics of 'Bi-criteria minimization for the permutation flowshop scheduling problem with machine-based learning effects'. Together they form a unique fingerprint.

Cite this