Non-approximability of precedence-constrained sequencing to minimize setups |
| |
Institution: | School of ISyE and College of Computing, Georgia Tech. Atlanta, GA 30332-0205, USA |
| |
Abstract: | It is a basic scheduling problem to sequence a set of precedence-constrained tasks to minimize the number of setups, where the tasks are partitioned into classes that require the same setup. We prove a conjecture in (Ph.D. Thesis, School of ISyE, Georgia Institute of Technology, August 1986; Oper. Res. 39 (1991) 1012) that no polynomial-time algorithm for this problem has constant worst-case performance ratio unless P=NP. A very simple algorithm has performance ratio . |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|