Minimizing makespan in an ordered flow shop with machine-dependent processing times

Byung Cheon Choi; Joseph Y.T. Leung; Michael L. Pinedo

doi:10.1007/s10878-010-9330-x

Minimizing makespan in an ordered flow shop with machine-dependent processing times

Byung Cheon Choi, Joseph Y.T. Leung, Michael L. Pinedo

Computer Science

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

We consider a generalization of the proportionate flow shop problem with the makespan objective. Each job has a processing requirement and each machine has a characteristic value. In our case, we assume that the time a job occupies a machine is equal to the processing requirement of the job plus a setup time that is equal to the characteristic value of that machine. In this paper, we consider permutation schedules and show that the problem is solvable in polynomial time when the number of machines is fixed.

Original language	English (US)
Pages (from-to)	797-818
Number of pages	22
Journal	Journal of Combinatorial Optimization
Volume	22
Issue number	4
DOIs	https://doi.org/10.1007/s10878-010-9330-x
State	Published - Nov 2011

All Science Journal Classification (ASJC) codes

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Keywords

Computational complexity
Machine-dependent processing times
Makespan
Proportionate flow shop

Access to Document

10.1007/s10878-010-9330-x

Cite this

@article{35f943315dae4590a80f28760bd8b942,

title = "Minimizing makespan in an ordered flow shop with machine-dependent processing times",

abstract = "We consider a generalization of the proportionate flow shop problem with the makespan objective. Each job has a processing requirement and each machine has a characteristic value. In our case, we assume that the time a job occupies a machine is equal to the processing requirement of the job plus a setup time that is equal to the characteristic value of that machine. In this paper, we consider permutation schedules and show that the problem is solvable in polynomial time when the number of machines is fixed.",

keywords = "Computational complexity, Machine-dependent processing times, Makespan, Proportionate flow shop",

author = "Choi, {Byung Cheon} and Leung, {Joseph Y.T.} and Pinedo, {Michael L.}",

note = "Funding Information: B.-C. Choi was supported by the Korea Research Foundation Grant KRF-2008-357-D00289. J.Y.-T. Leung was supported in part by the NSF Grant DMI-0556010. M.L. Pinedo was supported in part by the NSF Grant DMI-0555999.",

year = "2011",

month = nov,

doi = "10.1007/s10878-010-9330-x",

language = "English (US)",

volume = "22",

pages = "797--818",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - Minimizing makespan in an ordered flow shop with machine-dependent processing times

AU - Choi, Byung Cheon

AU - Leung, Joseph Y.T.

AU - Pinedo, Michael L.

N1 - Funding Information: B.-C. Choi was supported by the Korea Research Foundation Grant KRF-2008-357-D00289. J.Y.-T. Leung was supported in part by the NSF Grant DMI-0556010. M.L. Pinedo was supported in part by the NSF Grant DMI-0555999.

PY - 2011/11

Y1 - 2011/11

N2 - We consider a generalization of the proportionate flow shop problem with the makespan objective. Each job has a processing requirement and each machine has a characteristic value. In our case, we assume that the time a job occupies a machine is equal to the processing requirement of the job plus a setup time that is equal to the characteristic value of that machine. In this paper, we consider permutation schedules and show that the problem is solvable in polynomial time when the number of machines is fixed.

AB - We consider a generalization of the proportionate flow shop problem with the makespan objective. Each job has a processing requirement and each machine has a characteristic value. In our case, we assume that the time a job occupies a machine is equal to the processing requirement of the job plus a setup time that is equal to the characteristic value of that machine. In this paper, we consider permutation schedules and show that the problem is solvable in polynomial time when the number of machines is fixed.

KW - Computational complexity

KW - Machine-dependent processing times

KW - Makespan

KW - Proportionate flow shop

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

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

U2 - 10.1007/s10878-010-9330-x

DO - 10.1007/s10878-010-9330-x

M3 - Article

AN - SCOPUS:83555172646

SN - 1382-6905

VL - 22

SP - 797

EP - 818

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

Minimizing makespan in an ordered flow shop with machine-dependent processing times

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this