Flexible flow shop with dedicated buffers

Ernst, A; Fung, J; Singh, G; Zinder, Y

Flexible flow shop with dedicated buffers

Ernst, A Fung, J

Singh, G Zinder, Y

Permalink

Publication Type:: Journal Article
Citation:: Discrete Applied Mathematics, 2019, 261 pp. 148 - 163
Issue Date:: 2019-05-31

Closed Access

	Filename	Description	Size
	Flexible flow shop with dedicated buffers.pdf	Published Version	1.2 MB	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	Ernst, A	en_US
dc.contributor.author	Fung, J https://orcid.org/0000-0001-7352-4321	en_US
dc.contributor.author	Singh, G	en_US
dc.contributor.author	Zinder, Y https://orcid.org/0000-0003-2024-8129	en_US
dc.date.issued	2019-05-31	en_US
dc.identifier.citation	Discrete Applied Mathematics, 2019, 261 pp. 148 - 163	en_US
dc.identifier.issn	0166-218X	en_US
dc.identifier.uri	http://hdl.handle.net/10453/135337
dc.description.abstract	© 2018 Elsevier B.V. A two-stage flexible flow shop is considered, where first- and second-stage machines form disjoint pairs, each with a buffer. The buffer capacity varies from pair to pair, and the buffer requirement varies from job to job. Each job is to be assigned to a pair of machines for processing and uses the required amount of buffer from the start till the end of its processing. Operations have equal duration. It is shown that, unless P=NP, no polynomial-time algorithm guarantees a makespan less than 4∕3 of the optimal. The paper presents two integer linear programs, compared by means of computational experiments. Both approaches utilise as a subroutine the developed polynomial-time algorithm for the case of equal buffers.	en_US
dc.relation.ispartof	Discrete Applied Mathematics	en_US
dc.relation.isbasedon	10.1016/j.dam.2018.07.002	en_US
dc.subject.classification	Computation Theory & Mathematics	en_US
dc.title	Flexible flow shop with dedicated buffers	en_US
dc.type	Journal Article
utslib.citation.volume	261	en_US
utslib.for	0102 Applied Mathematics	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
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.publication-status	Published	en_US
pubs.volume	261	en_US

Abstract:

© 2018 Elsevier B.V. A two-stage flexible flow shop is considered, where first- and second-stage machines form disjoint pairs, each with a buffer. The buffer capacity varies from pair to pair, and the buffer requirement varies from job to job. Each job is to be assigned to a pair of machines for processing and uses the required amount of buffer from the start till the end of its processing. Operations have equal duration. It is shown that, unless P=NP, no polynomial-time algorithm guarantees a makespan less than 4∕3 of the optimal. The paper presents two integer linear programs, compared by means of computational experiments. Both approaches utilise as a subroutine the developed polynomial-time algorithm for the case of equal buffers.

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

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