مدیریت تولید و عملیات (Oct 2018)
Multi-Objective Hybrid Metaheuristic Search Algorithm for Distributed Reentrant Permutation Flow Shop Scheduling Via Considering Preventive Maintenance under Uncertainty
Abstract
Abstract: Distributing the production activities among the supply chain facilities with regard to the considered criteria can have a significant impact on the productive management. In this paper, a comprehensive mathematical model for reentrant permutation flow shop scheduling via considering a preventive maintenance and distributed jobs on different facilities is proposed. The uncertainty of the time of preventive maintenance operation is handled using robust optimization technique based on the uncertainty budget approach. Job assignment to production facilities and job scheduling are determined in the proposed model by considering multiple objectives include Cmax minimization, production cost minimization, and average tardiness. Due to the NP-hard nature of the proposed flow shop scheduling problem, a new hybrid meta-heuristic based on the novel adaptive large neighborhood search and the simulated annealing is adopted. The obtained results from an extensive numerical experimentation indicate the efficiency of the proposed model and solution algorithm to tackle the proposed problem. Introduction: In certain manufacturing industries, it has been observed that the classical assumption of flow shop scheduling, stating that each job visits each machine exactly once, is occasionally violated. The prime example can be noticed in the high-tech industries, i.e. semiconductor wafer fabrication in which the operation processes of the jobs are performed by re-visiting some workstations (Gupta & Sivakumar, 2006). The scheduling problem of this nature of processing is categorized as a distinct flow shop with reentrant line configuration, called reentrant flow shop scheduling (RFS) (Katragjini et. al., 2015). The significance of RFS is the processing layers l. Each layer begins from the first workstation and completes on the last workstation. It means that once a job finished a layer of a set of operations, it will repeat its process to the next layer starting on the first workstation until all operations are completed. The RFS scheduling has been an active research area and attracted a considerable attention since the past decade due to the development and improvement of high-tech industry. The complexity of RFS cannot be circumvented since it involves more operations than the classical flow shop. Moreover, the cyclic operations where the jobs with higher layers may overlap other jobs in the same work station are essential to be considered. As a result, these complexities have triggered the development of the efficient scheduling approaches to improve the system performance. Various researchers surveyed the scheduling techniques in semiconductor manufacturing and providing the global view on reentrant scheduling problems. Another form of RFS is reentrant permutation flow shop (RPFS) where at each level no passing is permitted, that is, not only the machine sequence the same for all jobs, but also the job sequence is the same for each machine (Rifai et al., 2016). Despite the enormous literature on the RFS, most studies -if not all- base their research on the assumption that the process only involves a single production line. Some studies exploredthe problem on hybrid RFS where the production stages have more than one machines available to process the jobs. Nevertheless, hybrid RFS is based on the single production line. Nowadays, single factory firms are less common, with multi-plant companies and supply chains taking a more important role in practice. Several literatures mentioned that multiple production lines with more than one production center, named as distributed manufacturing system, enables companies to achieve higher product quality, lower production costs and lower management risks. However, existing studies focused more on the economic field anddistributed finite capacity scheduling is seldom tackled. Materials and Methods:In this section, a novel hybrid meta-heuristic via considering the specific assumptions of the flow shop problem as a NP-hard problem is proposed. The proposed solution algorithm incorporates adaptive large neighborhood search and the simulated annealing algorithms. Various new construction and deconstruction neighborhood structures are applied in the proposed adaptive large neighborhood search algorithm. Details of the proposed algorithm is presented in Fig.1. Results and Discussion: The results of the proposed solution algorithm assessment are presented based on the two common performance assessment criteria which are proposed in the literature after 10 times runs of the applied solution algorithms. These criteria are the average number of obtained Pareto solution at each iteration of the algorithm and average number of Pareto solutions which are not dominated by solutions from other compared algorithms. In addition, computational time is considered as a third criteria for performance assessment of the proposed solution algorithm (See Table 1). Obtained results indicate the superiority of the proposed solution algorithm. Fig. 1- Peseudo code of the proposed solution algorithm Table 1- Performance assessment of the proposed solution algorithm Compared Alg. Proposed Alg. Pro. Compared Alg. Proposed Alg. Pro. 1 2 3 1 2 3 1 2 3 1 2 3 0.7270 39.30 72.01 0.4129 25.95 57.12 15 0.6120 18.71 3392.26 0.5114 13.80 3019.18 75 0.6991 34.43 180.23 0.5972 28.80 152.11 30 0.6523 18.01 5900.74 0.5304 11.20 5631.07 90 0.9009 48.23 479.19 0.6543 38.10 398.06 45 0.6914 15.23 6801.69 0.5713 11.83 6594.29 105 0.9207 47.3 1308.21 0.7810 36.30 1200.47 60 Conclusion: In this study, a comprehensive optimization model for an extended reentrant permutation flow shop scheduling via considering a preventive maintenance and distributed jobs on different facilities is proposed. To enhance the applicability of the proposed model, uncertainty of the time of preventive maintenance operation is handled using robust optimization technique based on the uncertainty budget approach. In the proposed mathematical model, multiple objectives include Cmax minimization, production cost minimization, and average tardiness are considered. The aim of the proposed model is to determine the job assignment to production facilities and job scheduling. A new hybrid meta-heuristic based on the novel adaptive large neighborhood search and the simulated annealing is applied as a consequence of the NP-hard nature of the proposed flow shop scheduling problem,. The obtained results from an extensive numerical experimentation indicate the efficiency of the proposed model and solution algorithm to tackle the proposed problem. References Gupta, A. K., & Sivakumar, A. I. (2006). “Job Shop Scheduling Techniques In Semiconductor Manufacturing”. Int. J. Adv. Manuf. Technol, 27(11), 1163-1169. Katragjini, K., Vallada, E., & Ruiz, R. (2015). “Rescheduling Flowshops Under Simultaneous Disruptions”. Paper presented at the 6th IESM Conference, Seville, Spain. Rifai, A. P., Nguyen, H. T., & Dawal, S. Z. M. (2016). “Multi-Objective Adaptive Large Neighborhood Search For Distributed Reentrant Permutation Flow Shop Scheduling”. Applied Soft Computing, 40(1), 42–57.
Keywords
