Zurück zu den Preprints des Jahres 2014


Scheduling Two Parallel Machines with a Single Server to Minimize Forced Idle Time

by Hasani, K.; Kravchenko, S.A.; Werner, F..

Series: 2014-05, Preprints

90B35 Scheduling theory, deterministic

In this paper, we consider the problem of scheduling a set of jobs on two parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the forced idle time. The problem of minimizing the forced idle time (interference problem) is known to be unary NP-hard for the case of two machines and equal setup and arbitrary processing times. We propose an MILP model and a heuristic algorithm which are tested on instances with up to 100,000 jobs. The computational results indicate that the algorithm has an excellent performance even for very large instances, where mostly an optimal solution is obtained within a very small computational time.

Scheduling, Parallel machines, Single server, Interference problem, Forced idle time