Scheduling jobs within time windows on identical parallel machines: New model and algorithms

详细信息    查看全文

• 作者：Gabrel ; Virginie
• 关键词：Fixed job scheduling ; Graphs ; Heuristics
• 刊名：European Journal of Operational Research
• 出版年：1995
• 出版时间：June 8, 1995
• 年：1995
• 卷：83
• 期：2
• 页码：320-329
• 全文大小：759 K

文摘

This article analyses the problem of scheduling non-preemptive jobs processed within time windows on k identical parallel machines. Each job can be completed on a sub-set of machines. The problem of determining if a particular set of jobs can be completed by the available machines is NP-complete. A new model and heuristics are proposed to solve this problem in two particular cases: first, the case in which each job has to be completed at fixed start and end times; second, the case in which each job can be completed within a time window larger than its processing time. Our approach deals with graph theory. It is based primarily on the independent set and partition into cliques concepts.