Zurück zu den Preprints des Jahres 2014


2014-01

Minimizing the Makespan for the Two-Machine Scheduling Problem with a Single Server: Two Algorithms for very Large Instances

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


Series: 2014-01, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
In this paper, we consider the problem of scheduling a given set of n jobs on two identical parallel machines with a single server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to minimize the makespan. For this unary NP-hard problem two fast algorithms with a complexity of O(n^2) are presented. The performance of these algorithms is evaluated for instances with up to 10000 jobs. Computational results indicate that the algorithms have an excellent performance for very large instances so that the objective function values obtained are very close to a lower bound, and in many cases even an optimal solution is achieved. The superiority over existing algorithms is obtained by sequencing the jobs on two machines so that the machine idle time and the server waiting time are minimized. In doing so, we follow the characteristics of an optimal solution resulting from its relevant lower bound.

Keywords:
Scheduling, Parallel machines, Single server, Lower bound, Idle time, Server waiting time