In the job shop scheduling problem (JSP), a finite set of jobs is processed on a finite set of machines under certain constraints, such that the maximum completion time of the jobs is minimized. In this paper, we describe a parallel greedy randomized adaptive search procedure (GRASP) with path-relinking for the JSP. Independent and cooperative parallelization strategies are described and implemented. Computational experience on a large set of standard test problems indicates that the parallel GRASP with path-relinking finds good-quality approximate solutions of the JSP.
The job shop scheduling problem (JSP) is a well-studied problem in combinatorial optimization. It consists in processing a finite set of jobs on a finite set of machines. Each job is required to complete a set of operations in a fixed order. Each operation is processed on a specific machine for a fixed duration. Each machine can process at most one job at a time and once a job initiates processing on a given machine it must complete processing on that machine without interruption. A schedule is a mapping of operations to time slots on the machines. The makespan is the maximum completion time of the jobs. The objective of the JSP is to find a schedule that minimizes the makespan.
Mathematically, the JSP can be stated as follows. Given a set View the MathML source of machines (where we denote the size of View the MathML source by View the MathML source) and a set View the MathML source of jobs (where the size of View the MathML source is denoted by View the MathML source), let View the MathML source be the ordered set of View the MathML source operations of job j, where σkj≺σk+1j indicates that operation σk+1j can only start processing after the completion of operation σkj. Let View the MathML source be the set of operations. Each operation σkj is defined by two parameters: View the MathML source is the machine on which σkj is processed and pkj=p(σkj) is the processing time of operation σkj. Defining t(σjk) to be the starting time of the kth operation View the MathML source, the JSP can be formulated as follows:
where Cmax is the makespan to be minimized.
A feasible solution of the JSP can be built from a permutation of View the MathML source on each of the machines in View the MathML source, observing the precedence constraints, the restriction that a machine can process only one operation at a time, and requiring that once started, processing of an operation must be uninterrupted until its completion. Once the permutation of View the MathML source is given, its feasibility status can be determined in View the MathML source time. The feasibility-checking procedure determines the makespan View the MathML source for feasible schedules [1]. Since, each set of feasible permutations has a corresponding schedule, the objective of the JSP is to find, among the feasible permutations, the one with the smallest makespan.
The JSP is NP-hard [2] and has also proven to be computationally challenging. Exact methods [3], [4], [5], [6] and [7] have been successful in solving small instances, including the notorious 10 × 10 instance of Fisher and Thompson [8], proposed in 1963 and only solved 20 years later. Problems of dimension 15 × 15 are still considered to be beyond the reach of today’s exact methods. For such problems there is a need for good heuristics. Surveys of heuristic methods for the JSP are given in [9] and [10]. These include dispatching rules reviewed in [11], the shifting bottleneck approach [3] and [12], local search [10], [13] and [14], simulated annealing [13] and [15], tabu search [1], [14] and [16], and genetic algorithms [17]. Recently, Binato et al. [18] described a greedy randomized adaptive search procedure (GRASP) for the JSP. A comprehensive survey of job shop scheduling techniques can be found in Jain and Meeran [19]. In this paper, we present a new parallel GRASP with path-relinking for the JSP.
The remainder of the paper is organized as follows. In Section 2, we describe the new GRASP, describing two construction mechanisms and a local search algorithm. Path-relinking for the JSP and its incorporation to a GRASP are described in Section 3. Two parallelization schemes are presented in Section 4. Computational results are reported in Section 5 and concluding remarks are made in Section 6.
We describe a new algorithm for finding approximate solutions to the JSP. This GRASP uses some of the ideas proposed in the GRASP of Binato et al. [18]. That GRASP applies an intensification strategy during the construction phase that uses information obtained from “good” solutions to implement a memory-based procedure to influence the construction phase. In the hybrid GRASP proposed in this paper, the intensification phase is moved to the end of each GRASP iteration and is done using path-relinking. Due to the high computational requirements of path-relinking, only solutions accepted by a quality criteria undergo this procedure. Furthermore, the new GRASP alternates between two semi-greedy algorithms to construct solutions, which produces a higher variety of initial solutions for the local search. The algorithm was evaluated on 66 standard test problems and was shown to produce optimal or near-optimal solutions on all instances.
We observe that the hybrid GRASP with path-relinking obtains a solution of a given quality faster than the pure GRASP. Therefore, the increase in the computational time of each GRASP iteration due to the computation of path-relinking is compensated by an increase in the method’s robustness. We also verify that the intensification applied after each GRASP iteration using path-relinking outperforms the intensification strategy used in Binato et al., which is applied during the construction phase.
We verify that the time to target sub-optimal solution of the proposed GRASPs fit well a two-parameter exponential distribution. Two parallelization strategies were proposed for the GRASP with path-relinking: an independent and a cooperative. The independent parallel strategy, as expected, shows a sub-linear speedup. The cooperative approach shows an approximate linear speedup for all instances tested, thus attesting that the extra time spent in communication among processes is compensated by an increase in solution quality.
