Exact and approximation algorithms for the tactical fixed interval scheduling problem
成果类型：
Article
署名作者：
Kroon, LG; Salomon, M; VanWassenhove, LN
署名单位：
Tilburg University; INSEAD Business School
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.4.624
发表日期：
1997
页码：
624-638
关键词：
摘要：
The Tactical Fixed Interval Scheduling Problem (TFISP) is the problem of determining the minimum number of parallel nonidentical machines, such that a feasible schedule exists for a given set of jobs. In TFISP, each job must belong to a specific job class and must be carried out in a prespecified time interval. The problem is complicated by the restrictions that (1) each machine can handle only one job at a time, (2) each machine can handle only jobs from a subset of the job classes, and (3) preemption is not allowed. In this paper we discuss the occurrence of TFISP in practice, we analyze the computational complexity of TFISP, and we present exact and approximation algorithms for solving TFISP. The paper concludes with a computational study.