An Integrated Heuristic for Machine Sequencing With Specific Reference to the Permutation Flow-Shop Scheduling Problem

Introduction

The flow-shop scheduling problem can be stated as follows: there are n jobs to be processed by m machines in an identical sequence on each machine. The usual objective is to minimize the completion time of the last job to leave the system, commonly termed the makespan (C_max). The flow-shop scheduling problem with m > 2 belongs to the class of combinatorial optimization problems known to be NP-hard in the strong sense (Garey et al., 1976). Hence, approximation methods are generally considered to solve these problems. There are many variations of the flow-shop scheduling problem (Baker, 1974). In this paper, the permutation flow-shop scheduling problem (PFSP) with makespan criterion is considered. In the PFSP after completing a job on one machine, the job is processed on the next machine or joins a queue if the machine is busy. All queues are assumed to operate under the first-in-first-out (FIFO) discipline. It means that a job cannot pass another job while waiting in a queue. Therefore, clearly there are n! possible schedules. Many heuristics have been proposed for this problem since Johnson’s (1954) pioneering work, including Page (1961), Palmer (1965), Campbell et al. (1970) and Nawaz et al. (1983). The collections of survey papers (Rajendran, 1995; Framinan et al., 2004; Ruiz and Maroto, 2005; Stafford et al., 2005) and books (French, 1982; Sule, 1997; Pinedo et al., 2015) summarize various developments in the subject. Here, we consider some of those methods that are most relevant to our discussion. Rajendran (1993) developed a heuristic for the total flowtime minimization criterion, similar to the NEH heuristic, which is based on arranging the jobs according to a particular method of ranking. Woo and Yim (1998) developed the heuristic for solving problems with the mean flowtime minimization criterion similar to the NEH heuristic but evaluating the partial sequences corresponding to the lowest flowtime. Davoud Pour (2001) proposed a procedure for makespan minimization based on an insertion method and the idea of job exchanging. Nagano and Moccellin (2002) proposed a heuristic to minimize the makespan, in which the initial list of jobs was assumed to be the final sequence obtained by the NEH heuristic, and then they applied the NEH’s insertion technique to construct a new sequence. They also modified the first step of the NEH heuristic by using a lower bound on the total waiting time for each job. Allahverdi and Aldowaisan (2002) developed a set of heuristics for minimizing total completion time. Their method constructs an initial sequence by applying the method of Woo and Yim (1998), and finally the obtained sequence is improved by a general pairwise interchange until it reaches a local optimum. Framinan and Leisten (2003) proposed a heuristic based on an adaptation of the NEH heuristic for flowtime minimization and applying a general pairwise interchange to improve the quality of the partial sequence obtained in the NEH’s insertion phase. Framinan et al. (2003), in their comprehensive study for producing an efficient initial order of the jobs for the NEH heuristic with multiple objectives, tried 177 distinct methods for ranking the jobs in the first phase of the NEH heuristic, of which the original NEH was just one. For makespan minimization, they concluded that the original NEH heuristic was the best method. This research thus confirmed the practical importance of the NEH heuristic for the PFSP with makespan criterion. Zheng and Yamashiro (2010) proposed a novel quantum differential evolutionary algorithm by merging particular evolutionary and local search strategies for permutation flow-shop scheduling problem minimizing the makespan and the total flowtime. Mirabi (2014) proposed a novel hybrid genetic algorithm using a modified approach to generate the initial population by an improved iterated swap procedure for the sequence-dependent permutation flow-shop scheduling problem minimizing the makespan. Liu et al. (2017) utilized the skewness of the processing times to construct a priority rule to the NEH heuristic for permutation flow-shop scheduling with the makespan criterion. Sioud and Gagné (2018) proposed an enhanced migrating bird optimization algorithm for the permutation flow-shop problem with sequence dependent setup times minimizing the makespan.