Minimizing Makespan on Identical Parallel Machines

Minimizing Makespan on Identical Parallel Machines

Abey Kuruvilla (Department of Business, University of Wisconsin-Parkside, Kenosha, WI, USA) and Giuseppe Paletta (Dipartimento di Economia e Statistica, Università della Calabria, Cosenza, Italy)
DOI: 10.4018/ijoris.2015010102


A heuristic algorithm that uses iteratively LPT and MF approaches on different job and machine sets constructed by using the current solution is developed to solve a classical multiprocessor scheduling problem with the objective of minimizing the makespan. Computational results indicate that the proposed algorithm is very competitive with respect to well-known constructive algorithms for a large number of benchmark instances.
Article Preview


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 pj>0, jJ 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||Cmax, see Graham, Lawler, Lenstra, & Rinnooy Kan, 1979.

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

P||Cmax 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||Cmax (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||Cmax are:

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018): 2 Released, 2 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing