The Open Operational Research Journal

2008, 2 : 18-24
Published online 2008 March 12. DOI: 10.2174/1874243200802010018
Publisher ID: TOORJ-2-18

Minimizing Makespan on Parallel Machines with Machine Eligibility Restrictions

Chien-Hung Lin and Ching-Jong Liao
Department of Industrial Management, National Taiwan University of Science and Technology, 43 Keelung Road, Section 4, Taipei, Taiwan 106.

ABSTRACT

In this paper, we consider a parallel machine problem where machines and jobs can be classified into two levels: high and low levels. A high-level machine can process all jobs while a low-level machine can process only low-level jobs. The objective of the problem is to minimize the makespan. This problem is a special case of the parallel machine problem with machine eligibility restrictions. The problem is NP-hard and a heuristic algorithm has recently been proposed. However, there are no algorithms in the literature that can solve the problem to optimality. In this paper, we develop such an exact algorithm by utilizing some useful properties inherent in the problem. Computational experiments show that the developed algorithm can find the optimal solution for various-sized problems in a short time.

Keywords:

Parallel machines, Machine eligibility, Scheduling.