A hybrid way to solve the task scheduling problem for multi-parallel machines with Time windows

Task Scheduling for Parallel Machines with Time Windows (TSPMTW) is a combinatorial optimization problem, when the number of variables and constraints on a large scale, it could become even more complex. A hybrid way combined Integer Programming (IP) with Constraint Programming (CP) techniques was presented. The theoretical basis of this approach is the common principles shared by IP and CP: strategies of searching and inference, strengthening and relaxation. In this method, the problem was decomposed through logic based Benders´ decomposition; the first part is an assignment problem which was treated as master problem, while the other is a series of single machine scheduling problem, we call it sub-problem; connections between master problem and sub-problem are general Benders´ cuts. The master problem was solved to generate the assignment scheme which had the maximum benefit, then make schedule for each machine according to the assignment scheme; if any conflict happens, Benders´ cuts were produced and sent to master problem as new constraints in the coming iterations. During the solving process of both master problem and sub-problem, the idea of integrating IP and CP tactics was implemented. This new algorithm has been tested by derived experiments under different scenarios, and these tests and comparisons yielded promising effect.