الگوریتم ژنتیک مبتنی بر اکتشاف برای مسائل برنامه ریزی جریان فروشگاه دو دستگاه بدون وقفه با زمان راه اندازی که حداکثر تاخیر را به حداقل می رساند

Machine scheduling problem has been extensively studied by researchers for many decades in view of its numerous applications on solving practical problems. Due to the complexity of this class of scheduling problems, various approximation solution approaches have been presented in the literature. In this paper, we present a genetic algorithm (GA) based heuristic approach to solve the problem of two machine no-wait flowshop scheduling problems that the setup time on the machines is class dependent, and the objective is to minimize the maximum lateness of the jobs processed. This class of machine scheduling problems has many practical applications in manufacturing industry, such as metal refinery operations, food processing industry and chemical products production processes, in which no interruption between subsequent processes is allowed and the products can be grouped into families. Extensive computation experiments have been conducted to evaluate the effectiveness of the proposed algorithm. Results show the proposed methodology is suitable to be adopted for the development of an efficient scheduling plan for this class of problems in real life application.

The problem of machine scheduling, with its extensive application and large impact on operating efficiency in both manufacturing and service industries, is one of the classical research topics that has been investigated since the 1950s. Variations of this class of scheduling problems include the number of machines in the system, number of stages the jobs need to be processed, job processing requirement, and the objective functions for optimization. In this paper, we study a variant of the classical machine scheduling problem, i.e., the two machine no-wait flowshop scheduling problem with class dependent setup time that minimizes the maximum lateness of the jobs. This class of machine scheduling problems has numerous applications in the steel processing industry where the metal slab must pass to the next operation without delay in order to maintain the temperature of the steel for further processing. Also, the dies for the forming process is suitable for a group of products that share the same physical characteristics, i.e., diameter of the pipe to be produced; setup is required only when a new product group is processed. Besides, the food processing industry also requires the materials are processed with no delay between processes, such as the canning operation must follow directly after the cooking process of the food in the canned food processing factory. Many other applications can be found that characterize this no-wait flowshop scheduling system, such as Just-in-time operations and chemical processing. In recent years, a considerable amount of research study has been devoted to the machine scheduling problems that consider no-wait flowshop operations. That is, the job has to be processed in the succeeding operation right after it finishes its processing in the preceding operation. This processing requirement applies to many production systems such as metal processing (Callahan, 1971), food processing, chemical processing (Reklaitis, 1982) and computer system operations (Reddi & Ramamoorthy, 1972). Rajendran (1994) presented a heuristic for a no-wait flowshop scheduling problem to minimize the makespan. The author compared several heuristics on this class of scheduling problems that considers up to 25 stages in the flowshop. Comprehensive survey on this class of machine scheduling problem can be found in Hall and Sriskandarajah (1996). Ruiz and Allahverdi (2009) recently presented the dominance relation for the three machine no-wait flowshop scheduling problems. They also develop several heuristic approaches based on the dominance relation as part of their heuristic. For the general flowshop scheduling problems, Gupta and Stafford (2006) provided a review on the study of this topic over the last 50 years. Besides the extensive research study on the no-wait flowshop scheduling problems, many researchers have also found interest in investigating the impact of the setup time on the machine before the jobs can be processed. And commonly, the setup time of the jobs is class dependent, and processing several jobs within the same product class requires the machine to be set up only once. This concept aligns with the product family grouping situation where similar products are grouped into a product family that requires the same setup on the machines to process this group of products. In such a situation, the scheduling of the jobs to be processed requires additional consideration on the setup time of the machines, where more products in the same class that are processed together can be beneficial to reduce the total setup time required, because this setup time is considered as non-productive time that should be minimized. However, we may consider to separate the processing of the products within the same class into several batches in sequence, especially when the delivery due date of the jobs is considered, in order to minimize the job lateness. One of the earlier studies on a two machine flowshop problem with separated setup time that considers job lateness is presented by Dileepan and Sen (1991). Later, Sidney et al. (2000) proposed a heuristic for solving a two machine no wait flow shops scheduling problem with anticipatory setup time on the second machine. The heuristic has a worst-case performance bound of 4/3 of the optimal solution on minimizing the makespan. A review on scheduling problem with setup consideration can be found in Allahverdi et al. (1999). Genoulaz (2000) presented several heuristics for solving the V-stage hybrid flow shop problems subject to job-precedence constraints, minimum time lags, setup and removal times and due dates, with the objective of minimizing the maximum lateness. In 2003, Lin and Liao (2003) presented a recursive based heuristic for solving the two-stage hybrid flow shop problem that considers sequence-dependent setup time and minimizes the weighted maximal tardiness. Al-Anzi and Allahverdi (2007) proposed a self-adaptive differential evolution heuristic for a two-stage assembly scheduling problem to minimize maximum lateness with setup times. They considered the case where there are multiple machines available at the first stage of the assembly operations, and also assumed the jobs can wait to be processed at the second stage. Later, they presented another paper to propose several heuristics for solving a two-stage assembly flowshop problem with a combined objective to minimize both the makespan and maximum lateness (Al-Anzi and Allahverdi, 2009). A survey on scheduling problems with batching or class based setup times can be found in Potts and Kovalyov (2000) and Allahverdi et al. (2008). Recently, Moslehi et al. (2009) presented a branch-and-bound based algorithm for solving the two machine flowshop scheduling problems that minimizes the sum of maximum earliness and tardiness. According to the three-field α/β/γ classification scheme proposed by Graham et al. (1979), the proposed scheduling problem we study in this paper is defined as F2/STsi,b, no-wait/Lmax, which denotes a two-machine no-wait flowshop problem with sequence independent batch setup time that minimizes the maximum lateness of the jobs. There are only a few studies found in the literature that addresses this specific problem. Wang and Cheng (2006) proposed a heuristic approach for solving this problem that uses forward merge and backward merge policies, which is based on an earliest due date initial schedule. Besides this article, the authors are not aware of any other study on this specific problem. The remaining sections of this paper are organized as follows: The problem description is presented in Section 2. In Section 3, we introduce the genetic algorithm based heuristic and detail the operation flow of our proposed approach. Section 4 presents the computational experiments including the data generation and computation results. Finally, we draw some concluding remarks and possible future direction in Section 5.

In this paper, we have developed a heuristic based on a genetic algorithm for solving two-machine no-wait flowshop scheduling problems with class based sequence independent setup times. Computational experiments have demonstrated that significant improvement is attainable using the proposed method when compared with other heuristic approaches. However, our proposed model and solution method still have several limitations. First, the problem we studied in this paper only focuses on the minimization of the maximum lateness. In fact, some real applications may need to optimize other performance measures, such as the makespan or the flow time of the jobs. One possible future direction is to consider a linear combination of multiple criteria as the objective function, such as combining total flow time and maximum lateness in order to better simulate the practical requirement of the applications adopted in different industries. Second, the computational time for solving the more difficult test problems (i.e., R=0.5) with 30 jobs takes about 20–25 min on average; therefore, another possible future direction is to fine tune the genetic algorithm based heuristic such that the convergence can further be enhanced so as to reduce the computational time requirement, in order to further improve the applicability of the proposed approach in solving larger scale real time scheduling problems. Third, although we present only the genetic algorithm based heuristic in this paper, in fact, other metaheuristic approaches may also be suitable for this class of machine scheduling problems. For instance, variations of the bacteria forging algorithm would be a suitable candidate for further consideration. Comparing different metaheuristic approaches for solving this machine scheduling problem is an important future research topic as we are aware that this class of scheduling problem is almost impossible to be solved optimally; thus an efficient heuristic or metaheuristic can be very beneficial and suitable to be adopted for solving real life machine scheduling problems. Finally, we have studied the specific two-machine no-wait flowshop scheduling problem in this paper, yet generalizing the model to consider other similar problems such as more stages in the flowshop or family class setup times that are sequence dependent is also a very challenging research topic worthy of further investigation.