Minimizing total completion time in a two-machine flowshop: Analysis of special cases

被引：48

作者：

Hoogeveen, JA

Kawaguchi, T

机构：

[1] Univ Utrecht, Dept Comp Sci, NL-3584 CH Utrecht, Netherlands

[2] Oita Univ, Dept Comp Sci & Intelligent Syst, Oita 87011, Japan

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 1999年 / 24卷 / 04期

关键词：

flowshop; total completion time; NP-hardness; heuristics; worst-case analysis; special case; polynomial algorithms;

D O I：

10.1287/moor.24.4.887

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the problem of minimizing total completion time in a two-machine flowshop. We present a heuristic with worst-case bound 2 beta/(alpha + beta), where alpha and beta denote the minimum and maximum processing time of all operations. Furthermore, we analyze four special cases: equal processing times on the first machine, equal processing times on the second machine, processing a job on the first machine takes time no less than its processing on the second machine, acid processing a job on the first machine takes time no more than its processing on the second machine. We prove that the first special case is NP-hard in the strong sense and present an O(n log n) approximation algorithm for it with worst-case bound 4/3. We repeat the easy polynomial algorithms for the cases two and three, and show that problem four is solvable in polynomial time as well.

引用

页码：887 / 910

页数：24