Abstract
The standard job shop problem is defined as follows. There are n jobs that have to be executed. Each
job consists of a chain of operations, which must be executed without interruption in the given order. For
each operation, it is given by which machine it should be executed, and how long this takes. The goal is
to minimize the time by which the last job has finished (makespan). We consider the flexible job shop
problem, in which each machine is replaced a station containing two or more parallel, identical machines;
an operation then has to be executed by exactly one of these dedicated identical machines.
We present an ILP-based solution method for this problem. We first prove a lower bound on the makespan,
and then feed this information into an ILP to find an optimal feasible schedule. We have applied two
methods to find a lower bound. The first one is based on a destructive method: the lower bound is equal to
the smallest makespan value for which we cannot show that there does not exist a feasible solution. The
second lower bound method is based on solving the LP-relaxation of an ILP-formulation that is based on
job patterns. Given the resulting lower bound LB, we formulate the job shop scheduling problem as a time
indexed integer linear program, to which we add the additional constraint that the makespan is equal to
LB. If we find a feasible solution, then we know it is optimal; if we can’t find one, then we know that we
can increase the lower bound to LB+1, and try again. Adding this constraint is crucial.
If turns out that this method works very well, especially in combination with the second lower bound. It
does not work for the standard job shop problem.
job consists of a chain of operations, which must be executed without interruption in the given order. For
each operation, it is given by which machine it should be executed, and how long this takes. The goal is
to minimize the time by which the last job has finished (makespan). We consider the flexible job shop
problem, in which each machine is replaced a station containing two or more parallel, identical machines;
an operation then has to be executed by exactly one of these dedicated identical machines.
We present an ILP-based solution method for this problem. We first prove a lower bound on the makespan,
and then feed this information into an ILP to find an optimal feasible schedule. We have applied two
methods to find a lower bound. The first one is based on a destructive method: the lower bound is equal to
the smallest makespan value for which we cannot show that there does not exist a feasible solution. The
second lower bound method is based on solving the LP-relaxation of an ILP-formulation that is based on
job patterns. Given the resulting lower bound LB, we formulate the job shop scheduling problem as a time
indexed integer linear program, to which we add the additional constraint that the makespan is equal to
LB. If we find a feasible solution, then we know it is optimal; if we can’t find one, then we know that we
can increase the lower bound to LB+1, and try again. Adding this constraint is crucial.
If turns out that this method works very well, especially in combination with the second lower bound. It
does not work for the standard job shop problem.
| Original language | English |
|---|---|
| Pages | 145 |
| Publication status | Published - 2013 |
| Event | International Conference on Operations Research 2013 - Rotterdam Duration: 5 Jan 2013 → … |
Other
| Other | International Conference on Operations Research 2013 |
|---|---|
| City | Rotterdam |
| Period | 5/01/13 → … |
Keywords
- scheduling
- column generation