Scheduling and planning

Mathematical programming or to be more precise Integer Programming is not always suggested as the best suited technology to solve scheduling problems. However with careful modeling it is possible to solve some very difficult problems. In this section we discuss a few examples.

The progressive party problem

The Progressive Party Problem is a famous problem long thought to be intractable for Mixed Integer Programming approaches. The problem is related to organizing a progressive party on a number of yachts. Guest crews stay at a host boat for a few drinks and then move on to the next. The idea is to create a schedule such that crews don't meet each other multiple times when they visit different parties. There have been several attempts to solve this model as a MIP and the consensus conclusion was that this model could not be solved as an integer programming problem. Some successes with constraint programming are reported. In this excersize we show that with careful modeling and a modern MIP solver we actually can solve the model in a reasonable time on a standard PC.

You can solve this model yourself by submitting the model expressed in AMPL to the NEOS Feaspump server.

Reference: Erwin Kalvelagen, On solving the progressive party problem as a MIP, Computers and Operations Research, Volume 30, Number 11, September 2003 , pp. 1713-1726 (14)

The social golfer problem

This is a related problem to the Progressive Party Problem. The original model is as follows: can we find a schedule for 32 golf players that play in groups of four. The games are weekly and we need an n week schedule such that each player does not play in the same group with any other player more than once. It can be seen that n=11 is too long: by then a player sees 3 × 11 = 33 other players. For a long time n=9 solutions are available, but a solution for n=10 weeks was never found using integer or constraint programming.

A schedule produced by Microsoft Solver Foundation

A parallel machine scheduling problem

The parallel machine scheduling problem with unrelated machines and sequence dependent setup times is a challenging sequencing problem. The industrial application dealt with scheduling jobs on extruder lines, where the setup times depent (largely) on the colors of the jobs: a white job followed by a black job is cheaper than the other way around. The implemented model has a number of features such as optimizing per line individually before dealing with the complete model where a MIPSTART option is used to start from a good integer solution. In addition an automatic decomposition scheme is employed if we can detect independent subproblems (jobs can execute only on certain lines). The model employs a continuous time representation, so no discretization is used, and no time periods are used as a variable index. The data comes from an Oracle database and the optimizer (GAMS/Cplex) runs underneath a larger scheduling system. The GANTT charts are produced by the charting facility of the GAMS IDE.

A conference scheduling problem

A small 5-day conference is to be scheduled such that the preferences of attendees are maximized. The problem is modeled using a standard "cube" formulation, resulting in in a large but relatively easy to solve problem. We solve here with Cplex on four threads. The model contains the exact problem statement.

Job Shop Scheduling

Job Shop Scheduling problems can be difficult to solve. An example is ft10 with 10 jobs and 10 machines. An optimal solution for this problem was not known for 25 years. Nowadays with the best MIP solvers such as Gurobi and Cplex we can solve this problem formulated as a standard MIP model in less than 5 minutes. Some VBA code has been developed to produce GANTT charts in Excel.

In practical cases, proper modeling can make a lot of difference in performance and reliability in the solution of the optimization models.

Column Generation Approach

For some larger problems an elegant and powerful technique called Column Generation can be used to efficiently create near-optimal schedules. This approach has been used effectively to generate rosters and time tables in different application areas.