Abstract
This paper addresses the total completion time minimization in a two-stage differentiation flowshop where the sequences of jobs per type are predetermined. The two-stage differentiation flowshop consists of a stage-1 common machine and m stage-2 parallel dedicated machines. The goal is to determine an optimal interleaved processing sequence of all jobs at the first stage. We propose an O(m2∏mk=1nm+1k) dynamic programming algorithm, where nk is the number of type-k jobs. The running time is polynomial when m is constant.
Original language | English |
---|---|
Pages (from-to) | 208-212 |
Number of pages | 5 |
Journal | Information Processing Letters |
Volume | 111 |
Issue number | 5 |
DOIs | |
State | Published - 1 Feb 2011 |
Keywords
- Design of algorithms
- Differentiation flowshop
- Dynamic programming
- Fixed sequences
- Scheduling