A minimum-cost network flow approach to preemptive parallel-machine scheduling

We model and solve the problems of preemptive scheduling of n independent jobs with release dates on m parallel machines with machine availability and eligibility constraints to minimize the makespan and maximum lateness as the minimum-cost network flow problem. We show that the approach can be extended to solve the corresponding scheduling problems on two uniform parallel machines.

► A minimum-cost network flow approach to preemptive parallel-machines scheduling problem is proposed. ► The job release dates, machine availability and eligibility constraints are considered. ► The approach can be applied to tackle a variety of preemptive scheduling problems with special structure.