Multistage hybrid flowshop scheduling with identical jobs and uniform parallel machines
type: Item
instance of: scholarly article
title: Multistage hybrid flowshop scheduling with identical jobs and uniform parallel machines
zbMATH Open document ID: 0963.90030
author: Sushil Verma
author: Maged Dessouky
published in: Journal of Scheduling
publication date: 2001-07-09T00:00:00Z
review text: The single-stage scheduling problem to minimize the makespan of identical jobs with general release times on uniform parallel machines is known to be solvable in polynomial time using the Latest Start Time (LST) rule to determine the optimal schedule. In this paper, the authors first show that the two-stage problem is NP-hard using a known result that the three-stage problem with equal job release times is NP-hard. The rest of the paper consists of two parts. In the first part, they compare the extension of the LST rule to the general multistage problem with other heuristics. The authors compare the heuristics based on the theoretically determined worst-case absolute error bound and on the experimentally determined average deviation from a developed lower bound. The analysis shows that in the presence of many stages, the LST rule does not perform as well as the other heuristics even though they are suboptimal for the single-stage problem. In the second part of this paper, the authors present a \((2+\varepsilon)\)-approximation algorithm for the multi-stage problem.
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 1308990
zbMATH Keywords: latest start time rule
zbMATH Keywords: two-stage problem
zbMATH Keywords: NP-hard
MaRDI profile type: Publication
cites work: Minimizing makespan in hybrid flowshops
cites work: Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time
cites work: Two-Stage, Hybrid Flowshop Scheduling Problem
cites work: Scheduling a two-stage hybrid flowshop with separable setup and removal times
cites work: A state-of-the-art review of parallel-machine scheduling research
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Scheduling identical jobs on uniform parallel machines
cites work: Flowshop scheduling with identical jobs and uniform parallel machines
cites work: Q4040221
DOI: 10.1002/(SICI)1099-1425(199905/06)2:3%3C135::AID-JOS21%3E3.0.CO;2-L
description: scientific article; zbMATH DE number 1308990