Flow shop with job–dependent buffer requirements—a polynomial–time algorithm and efficient heuristics

Kononov, A; Memar, J; Zinder, Y

Flow shop with job–dependent buffer requirements—a polynomial–time algorithm and efficient heuristics

Kononov, A

Memar, J

Zinder, Y

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2019, 11548 LNCS pp. 342 - 357
Issue Date:: 2019-01-01

Closed Access

	Filename	Description	Size
	2019_Book_MathematicalOptimizationTheory.pdf	Published version	21.38 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	Kononov, A https://orcid.org/0000-0001-6144-0251	en_US
dc.contributor.author	Memar, J https://orcid.org/0000-0003-2395-1450	en_US
dc.contributor.author	Zinder, Y https://orcid.org/0000-0003-2024-8129	en_US
dc.date.accessioned	2020-03-16T01:02:55Z
dc.date.available	2020-03-16T01:02:55Z
dc.date.issued	2019-01-01	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2019, 11548 LNCS pp. 342 - 357	en_US
dc.identifier.isbn	9783030226282	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/139318
dc.description.abstract	© Springer Nature Switzerland AG 2019. The paper is concerned with the two-machine flow shop, where each job needs storage space (a buffer requirement) during the entire time of its processing. The buffer requirement is determined by the duration of job’s first operation. The goal is to minimise the time needed for the completion of all jobs. This scheduling problem is NP-hard in the strong sense even for very restricted cases such as the case with a given order of jobs processing on one of the machines. The paper contributes to the efforts of establishing the borderline between the NP-hard and polynomial-time solvable cases by proving that there exists a polynomial-time algorithm which constructs an optimal schedule if the duration of each operation does not exceed one-fifth of the buffer capacity. The presented polynomial-time algorithm is used as a basis for a heuristic for the general case. This heuristic is complemented by a Lagrangian relaxation based heuristic and a bin-packing based constructive heuristic. The heuristics are tested by computational experiments.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.relation.isbasedon	10.1007/978-3-030-22629-9_24	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Flow shop with job–dependent buffer requirements—a polynomial–time algorithm and efficient heuristics	en_US
dc.type	Conference Proceeding
utslib.citation.volume	11548 LNCS	en_US
utslib.for	010206 Operations Research	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	11548 LNCS	en_US

Abstract:

© Springer Nature Switzerland AG 2019. The paper is concerned with the two-machine flow shop, where each job needs storage space (a buffer requirement) during the entire time of its processing. The buffer requirement is determined by the duration of job’s first operation. The goal is to minimise the time needed for the completion of all jobs. This scheduling problem is NP-hard in the strong sense even for very restricted cases such as the case with a given order of jobs processing on one of the machines. The paper contributes to the efforts of establishing the borderline between the NP-hard and polynomial-time solvable cases by proving that there exists a polynomial-time algorithm which constructs an optimal schedule if the duration of each operation does not exceed one-fifth of the buffer capacity. The presented polynomial-time algorithm is used as a basis for a heuristic for the general case. This heuristic is complemented by a Lagrangian relaxation based heuristic and a bin-packing based constructive heuristic. The heuristics are tested by computational experiments.

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

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