Minimizing Makespan on Identical Parallel Machines

Introduction

The scheduling problem of independent jobs on parallel machines is one of the most studied problem in combinatorial optimization both for its theoretical interest and for its practical aspect in many real world applications (see Lee, Lei & Pinedo, 1997). Still it continues to interest many researchers (Huang, Zhang, & Alexander, 2012; Montoya-Torres, Gómez-Vizcaíno, Solano-Charris, & Paternina-Arboleda, 2010; Mungan, Yu, Sarker, & Rahman, 2012; Wang, Moraga, & Ghrayeb, 2011). In this paper we address the classical problem of scheduling a set J={1,...,j,...,n} of n independent jobs, with positive processing times p_j>0, j∈J and simultaneously available, on a set M={1,...,i,...,m} of m identical parallel machines. Each machine can process at the most one job at a time, and each job must be processed without interruption by exactly one of the m machines. The paper considers the problem of finding the schedule that minimizes the maximum job completion time (makespan). This problem is denoted in the literature as P||C_max, see Graham, Lawler, Lenstra, & Rinnooy Kan, 1979.

A feasible solution (schedule) for P||C_max is represented by an m-partition S={S₁,..., S_i,...,S_m} of the set J, where each S_i represents the subset of jobs assigned to the machine i, i∈M. For each feasible solution S, the work-loads of the machines are represented by the m-set C(S)={C(S₁),...,C(S_i),...,C(S_m)}, where C(S_i)=∑_j∈Si p_j is the work-load of machine i∈M. In other words, C(S_i) represents the completion time of the latest job assigned to the machine i∈M. For each schedule S, C_max(S)=max_i∈M{C(S_i)} denotes the makespan associated with the solution S.

P||C_max is strongly NP-Hard for an arbitrary m≥2 (see Garey & Johnson, 1979). It is supposed that n>m≥2 to avoid trivialities. Exact algorithms have been proposed in Blazewicz, 1987; Dell'Amico & Martello, 1995; Mokotoff, 2004; Dell'Amico, Iori, Martello, & Monaci, 2008. However for large instances it needs to design good heuristic algorithms to obtain, in reasonable time, solutions that are probably close to the optimum. Improvement heuristics have been proposed in Finn & Horowitz, 1979; Langston, 1982; Fatemi Ghomi & Jolai Ghazvini, 1998. In addition, metaheuristic procedures have been developed in Hübscher & Glover, 1994; Thesen, 1998; Dell'Amico et al., 2008; Paletta & Vocaturo, 2011.

Many polynomial time constructive approaches, having a known worst-case performance ratio, have been developed to solve P||C_max (for an overview, see Cheng & Sin, 1990; Lawler, Lenstra, Rinnooy Kan, & Shmoys, 1993; Hoogeveen, Lenstra, & Van de Velde, 1997; Chen, Potts, & Woeginger, 1998; Mokotoff, 2001). The most important constructive approaches to solve P||C_max are: