Parallel machine scheduling

20 April 2021

Yet Another Math Programming Consultant (YAMPC) has a couple of interesting articles exploring different model formulations for machine scheduling problems:

• Parallel machine scheduling I, two formulations.
• Parallel machine scheduling II, three more formulations.

The situation involves scheduling 50 jobs on 4 parallel machines, with precedence relationships between jobs and multiple weighted objectives.

Five different formulations are analyzed:

• Model 1. Jobs are scheduled in discrete time slots.
• Model 2. Jobs are scheduled in continuous time.
• Model 3. A variation of Model 1.
• Model 4. A more complex variation of Model 2.
• Model 5. A positional, rather than time-based, model.

In this situation, Model 1 is the simplest and it performs the best – by a substantial margin.

YAMPC concludes that choosing the right formulation can pay off (though often we need to do numerical tests to determine which formulation is best), and having different formulations is an excellent debugging tool as they give us confidence that the results are correct.