Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/25167
Title: Hybrid flow-shop scheduling problems with multiprocessor task systems
Authors: Oguz, C
Zinder, Y
Do, VH
Janiak, A
Lichtenstein, M
Keywords: Complexity theory
Dynamic programming
Scheduling
Tabu search
Issue Date: 2004
Publisher: Elsevier
Source: European journal of operational research, 2004, v. 152, no. 1, p. 115-131 How to cite?
Journal: European journal of operational research 
Abstract: Hybrid flow-shop problems and problems with multiprocessor task systems have remained subject of intensive research over several years. Hybrid flow-shop problems overcome one of the limitations of the classical flow-shop model by allowing parallel processors at each stage of task processing. Problems with multiprocessor task systems relax the limitation of the classical parallel processor model by permitting tasks that require more than one processor simultaneously. The great deal of interest for both types of problem, besides their obvious theoretical significance, was inspired by needs of various manufacturing and computing systems. In this paper we consider a model which amalgamates both above-mentioned generalizations. We show that, without precedence constraints and under the assumption that all processing times are bounded above, the makespan minimization problem is solvable in polynomial time, whereas the introduction of precedence constraints makes even the simplest version of this problem NP-hard. For the arbitrary processing time task systems, we present an approximation algorithm based on the idea of tabu search and discuss the results of computational experiments, which were performed to analyze the algorithm's efficiency and sensitivity to variation in the input data.
URI: http://hdl.handle.net/10397/25167
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/S0377-2217(02)00644-6
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

66
Last Week
1
Last month
0
Citations as of Oct 8, 2017

WEB OF SCIENCETM
Citations

52
Last Week
0
Last month
0
Citations as of Oct 15, 2017

Page view(s)

35
Last Week
0
Last month
Checked on Oct 15, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.