APPROXIMATION ALGORITHMS FOR FIXED JOB SCHEDULE PROBLEMS
成果类型：
Article
署名作者：
FISCHETTI, M; MARTELLO, S; TOTH, P
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.1.S96
发表日期：
1992
页码：
S96-S108
关键词：
摘要：
We consider two generalizations of the fixed job schedule problem, obtained by imposing a bound on the spread-time or on the working time of each processor. These NP-hard problems, studied by the authors in previous works, can arise in bus driver scheduling. We introduce several polynomial-time approximation algorithms, give efficient implementations for them, and analyze their complexity and worst case performance. The average behavior is also investigated through extensive computational experiments.