SCHEDULING JOBS WITHIN TIME WINDOWS ON IDENTICAL PARALLEL MACHINES - NEW MODEL AND ALGORITHMS

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.