Parallel machine scheduling problem with time windows: a constraint programming and tabu search hybrid approach

Problem of scheduling nonpreemptable jobs which require a machine from a set of parallel, nonhomogeneous machines is considered. For a given job there are known: its processing time, its priority, the machine subset satisfying its processing demands, and multi machine-dependent time windows during which it can be processed. The scheduling problem is an over constrained problem, and the optimization criterion is to maximize the contribution of jobs scheduled. In the paper, a constraint based model of the problem is first given, and then, an algorithm integrating constraint programming (CP) and tabu search technique is presented to solve the model. The CP system is used to check the validity of solutions and determine the values of constrained variables, and the tabu search meta heuristics is used to perform the search process. For checking each neighborhood move's validity efficiently, a method called forward time slack and its related theorem are also given. The computational experiment for random generated benchmarks has been carried out on a PC computer with a P4 1.5G processor.