Flowshop scheduling with dominant machines
type: Item
instance of: scholarly article
title: Flowshop scheduling with dominant machines
zbMATH Open document ID: 0826.90064
DOI: 10.1016/0305-0548(94)E0007-T
author: Johnny C. Ho
author: Jatinder N. D. Gupta
published in: Computers \& Operations Research
publication date: 1995-11-23T00:00:00Z
review text: This paper considers two special cases of the permutation flowshop scheduling problem: the flowshop with an increasing series of dominating machines \((M_1\prec M_2\prec\cdots\prec M_m)\) and the flowshop with a decreasing series of dominating machines \((M_1\succ M_2\succ\cdots\succ M_m)\). Machine \(a\) dominates machines \(b\) \((M_a\succ M_b)\) if \(\min\{t(i, a)\mid i\in \mathbb{N}\}\geq \max\{t(i, b)\mid i\in \mathbb{N}\}\), where \(t(i, a)\), the processing time of job \(i\) on machine \(a\) and \(N= \{1,2,\dots, n\}\), set of all \(n\) jobs. The authors discuss these two special cases with the following objective functions: the maximum flowtime (makespan) \(C_{\max}\), the mean flowtime (equivalent to the sum of completion times of all jobs at the last machine \(\sum C_i\)), the sum of completion times of the last job of all machines \(\sum C_{[n]j}\), the total number of tardy jobs \(\sum U_i\), the maximum lateness \(L_{\max}\) or tardiness \(T_{\max}\). Based on the analysis of the special cases, simple polynomial-time algorithms are given.
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 710311
zbMATH Keywords: machine dominance
zbMATH Keywords: makespan
zbMATH Keywords: permutation flowshop scheduling
zbMATH Keywords: maximum flowtime
zbMATH Keywords: mean flowtime
zbMATH Keywords: sum of completion times
zbMATH Keywords: total number of tardy jobs
zbMATH Keywords: maximum lateness
zbMATH Keywords: tardiness
zbMATH Keywords: polynomial-time algorithms
reviewed by: G. Schulz
MaRDI profile type: Publication
cites work: Optimal two- and three-stage production schedules with set-up time included
cites work: Q4198056
cites work: A concise survey of efficiently solvable special cases of the permutation flow-shop problem
cites work: Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times
cites work: Ordered Flow Shop Problems with no In-Process Waiting: Further Results
cites work: Focused Scheduling in Proportionate Flowshops
cites work: Flow-shops with a dominant machine
cites work: Q3212909
cites work: Flowshop Sequencing Problem with Ordered Processing Time Matrices
cites work: Optimal schedules for special structure flowshops
cites work: An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
cites work: Q4658190
full work available at URL: 0305-0548(94)e0007-t
OpenAlex ID: W2039783295
description: scientific article; zbMATH DE number 710311