Flowshop scheduling with dominant machines (Q1342341)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Flowshop scheduling with dominant machines |
scientific article |
Statements
Flowshop scheduling with dominant machines (English)
0 references
23 November 1995
0 references
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.
0 references
machine dominance
0 references
makespan
0 references
permutation flowshop scheduling
0 references
maximum flowtime
0 references
mean flowtime
0 references
sum of completion times
0 references
total number of tardy jobs
0 references
maximum lateness
0 references
tardiness
0 references
polynomial-time algorithms
0 references
0 references
0 references