Total completion time minimization in a 2-stage differentiation flowshop with fixed sequences per job type

Miao-Tsong Lin; F. J. Hwang

doi:10.1016/j.ipl.2010.11.021

Total completion time minimization in a 2-stage differentiation flowshop with fixed sequences per job type

Miao-Tsong Lin, F. J. Hwang

Department of Information Management and Finance

Research output: Contribution to journal › Article

19 Scopus citations

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(m²∏^m_k=1n^m+1_k) 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	https://doi.org/10.1016/j.ipl.2010.11.021
State	Published - 1 Feb 2011

Keywords

Design of algorithms
Differentiation flowshop
Dynamic programming
Fixed sequences
Scheduling

Access to Document

10.1016/j.ipl.2010.11.021

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Total completion time minimization in a 2-stage differentiation flowshop with fixed sequences per job type'. Together they form a unique fingerprint.

Cite this

Lin, M-T., & Hwang, F. J. (2011). Total completion time minimization in a 2-stage differentiation flowshop with fixed sequences per job type. Information Processing Letters, 111(5), 208-212. https://doi.org/10.1016/j.ipl.2010.11.021

@article{7e2a21900a30475b9a5e3bcc5e9fa6cb,

title = "Total completion time minimization in a 2-stage differentiation flowshop with fixed sequences per job type",

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.",

keywords = "Design of algorithms, Differentiation flowshop, Dynamic programming, Fixed sequences, Scheduling",

author = "Miao-Tsong Lin and Hwang, {F. J.}",

year = "2011",

month = feb,

day = "1",

doi = "10.1016/j.ipl.2010.11.021",

language = "English",

volume = "111",

pages = "208--212",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - Total completion time minimization in a 2-stage differentiation flowshop with fixed sequences per job type

AU - Lin, Miao-Tsong

AU - Hwang, F. J.

PY - 2011/2/1

Y1 - 2011/2/1

N2 - 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.

AB - 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.

KW - Design of algorithms

KW - Differentiation flowshop

KW - Dynamic programming

KW - Fixed sequences

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=78649628117&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2010.11.021

DO - 10.1016/j.ipl.2010.11.021

M3 - Article

AN - SCOPUS:78649628117

VL - 111

SP - 208

EP - 212

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 5

ER -