Total completion time minimization in two-machine flow shop scheduling problems with a fixed job sequence

Hwang, FJ; Kovalyov, MY; Lin, BMT

Total completion time minimization in two-machine flow shop scheduling problems with a fixed job sequence

Hwang, FJ

Kovalyov, MY Lin, BMT

Permalink

Publication Type:: Journal Article
Citation:: Discrete Optimization, 2012, 9 (1), pp. 29 - 39
Issue Date:: 2012-02-01

Closed Access

	Filename	Description	Size
	2012001330OK.pdf		514.55 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Hwang, FJ https://orcid.org/0000-0002-1741-5590	en_US
dc.contributor.author	Kovalyov, MY	en_US
dc.contributor.author	Lin, BMT	en_US
dc.date.issued	2012-02-01	en_US
dc.identifier.citation	Discrete Optimization, 2012, 9 (1), pp. 29 - 39	en_US
dc.identifier.issn	1572-5286	en_US
dc.identifier.uri	http://hdl.handle.net/10453/43745
dc.description.abstract	This paper addresses scheduling n jobs in a two-machine flow shop to minimize the total completion time, subject to the condition that the jobs are processed in the same given sequence on both machines. A new concept of optimal schedule block is introduced, and polynomial time dynamic programming algorithms employing this concept are derived for two specific problems. In the first problem, the machine-2 processing time of a job is a step increasing function of its waiting time between the machines, and a decision about machine-1 idle time insertion has to be made. This problem is solved in O( n2) time. In the second problem, the jobs are processed in batches and each batch is preceded by a machine-dependent setup time. An O( n5) algorithm is developed to find an optimal batching decision. © 2011 Elsevier B.V. All rights reserved.	en_US
dc.relation.ispartof	Discrete Optimization	en_US
dc.relation.isbasedon	10.1016/j.disopt.2011.11.001	en_US
dc.subject.classification	Operations Research	en_US
dc.title	Total completion time minimization in two-machine flow shop scheduling problems with a fixed job sequence	en_US
dc.type	Journal Article
utslib.citation.volume	1	en_US
utslib.citation.volume	9	en_US
utslib.for	0102 Applied Mathematics	en_US
utslib.for	0101 Pure Mathematics	en_US
utslib.for	0103 Numerical and Computational Mathematics	en_US
dc.location.activity	Brussels, Belgium
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	closed_access
pubs.issue	1	en_US
pubs.publication-status	Published	en_US
pubs.volume	9	en_US

Abstract:

This paper addresses scheduling n jobs in a two-machine flow shop to minimize the total completion time, subject to the condition that the jobs are processed in the same given sequence on both machines. A new concept of optimal schedule block is introduced, and polynomial time dynamic programming algorithms employing this concept are derived for two specific problems. In the first problem, the machine-2 processing time of a job is a step increasing function of its waiting time between the machines, and a decision about machine-1 idle time insertion has to be made. This problem is solved in O( n2) time. In the second problem, the jobs are processed in batches and each batch is preceded by a machine-dependent setup time. An O( n5) algorithm is developed to find an optimal batching decision. © 2011 Elsevier B.V. All rights reserved.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/28818