Logical Benders for Scheduling
John Mitchell

Some classes of scheduling problems can be solved by a type of logical Benders decomposition popularized by Hooker [231].

Consider a problem where we have to assign J jobs to m machines and then schedule the jobs on the machines. Each job j has a release time aj and a due date bj > aj. Work cannot start on job j until time aj and it must be finished by time bj. It also has a processing time depending on the machine i chosen, denoted pij. We have a cost cij for processing job j on machine i and the objective is to minimize the sum of these costs.

A Benders-type of approach to this problem is to construct a Master Problem that assigns jobs to machines and then have separate subproblems for each machine that schedule the jobs assigned to that machine. If the subproblem is infeasible then a constraint is fed back to the Master Problem and the Master Problem is solved again.

We can write the Master Problem as

           ∑     ∑
minx          mi=1   Jj=1 cijxij
           ∑m
subject to     i=1 xij = 1
           constraints to prevent invalid assignments  to machine  i

           x binary
(1)

Given a solution to the Master Problem  (1), the subproblem for machine i has to determine start times for each job j assigned to it in order to meet the time window constraints. If the subproblem is infeasible then there is a time interval [a,b] which is too short for the jobs assigned to the machine. More specifically, let J(i) be the jobs assigned to machine i and let

Jba(i) := {i ∈ J(i) : a ≤ aj and bj ≤ b}.
(2)

If

 ∑
     pij > b - a
j∈Jba(i)
(3)

then this set of jobs cannot all be assigned to machine i. Denote this set of jobs by Ĵ. A valid constraint for the Master Problem is then

∑
    (1 - xij) ≥ 1.
  ˆJ
(4)

This forces xij = 0 for at least one of the jobs in Ĵ, thus preventing the assignment of this complete set of jobs to machine i.

In order to speed up the algorithm, it is desirable to sparsify the set Ĵ, that is, include as few jobs in the set as possible.

The structure of this Benders algorithm is different from the others we have considered in that the subproblem is an integer program. Thus, we cannot exploit LP duality in the construction of cuts for the Master Problem. Instead, we have to use logical arguments to construct valid constraints for the Master Problem. Hooker refers to the arguments as infeasibility proofs; he generalizes the idea of an LP dual to an inference dual.

References

[1]   J. N. Hooker. An integrated method for planning and scheduling to minimize tardiness. Constraints, 11(2–3):139–157, 2006.

[2]   J. N. Hooker. Planning and scheduling by logic-based benders decomposition. Operations Research, 55(3):588–602, 2007.

[3]   J. N. Hooker and G. Ottosson. Logic-based Benders decomposition. Mathematical Programming, 96(1):33–60, 2003.