مقاله سال ۲۰۱۶

 مجله امگا – Omega

The flowshop scheduling problem (FSP) has been one of the most intensively discussed classes of problems in operations research literature over the past five decades [1–۵]. Of particular practical interest is variants of FSPs, called no-wait FSPs (NWFSPs), that are widely applied in various industries, such as the chemicals, plastics, metals, electronics, pharmaceuticals, and foodprocessing industries [6,7]. For technological reasons, in these industries, no in-process waiting is allowed between any two consecutive machines, such that once the processing of a job begins, subsequent processing must be continuously carried out on all machines with no interruption until completion. This paper focuses on the NWFSP with the objective of minimizing the makespan, which can be written as Fm j nwtj Cmax using the standard 3-tuple notation of Graham et al. [8], where Fm is a flowshop with m machines, nwt denotes the no-wait restriction and Cmax indicates that the objective is to minimize the makespan. This problem is a member of the set of strongly NP-hard problems for three or more machines [9].

In view of the significance of the Fm j nwtj Cmax problem in both theory and engineering applications, effective and efficient algorithms for solving it are required. Gilmore and Gomory solved the two-machine case of the Fm j nwtj Cmax problem using an Oðn log nÞ time algorithm with a sub-tour patching technique [10]. Reddi and Ramamoorthy [11] and Wismer [12] were the first to address the Fm j nwtj Cmax problem with three or more machines. Many researchers have since attempted to develop effective and efficient algorithms for solving this problem. An early comprehensive survey of the Fm j nwtj Cmax problem can be found in Hall and Sriskandarajah [13].

With respect to exact methods, Selen and Hott [14] presented a mixed integer goal programming model for solving the multiobjective NWFSP. Van der Veen and Van Dal [15] have proven that some special cases of NWFSPs are solvable using polynomial time solution algorithms if the processing times on all but two machines are fixed. To the best of our knowledge, no exact method has yet been proposed for solving the Fm j nwtj Cmax problem. Given the NP-nature of this problem, all previous studies of this topic have focused on developing heuristic algorithms in order to find good (although not necessarily optimal) solutions to this intractable problem in a relatively short time.