From fluid relaxations to practical algorithms for job shop scheduling: The makespan objective (Q1600095)

The authors consider the problem of scheduling non-preemptable jobs in a job shop systems in order to minimize schedule length. The presented approach is based on the ideas from queuing theory used in communication networks. The presented algorithm, called the fluid synchronization algorithm, produces approximate schedules with a relative error being competitive to other known dispatching rules.