الگوریتم ژنتیک چند سطحی برای منابع محدود مسئله برنامه ریزی بازگذشتی در جریان فروشگاه

The re-entrant flow shop scheduling problem (RFSP) is regarded as a NP-hard problem and attracted the attention of both researchers and industry. Current approach attempts to minimize the makespan of RFSP without considering the interdependency between the resource constraints and the re-entrant probability. This paper proposed Multi-level genetic algorithm (GA) by including the co-related re-entrant possibility and production mode in multi-level chromosome encoding. Repair operator is incorporated in the Multi-level genetic algorithm so as to revise the infeasible solution by resolving the resource conflict. With the objective of minimizing the makespan, Multi-level genetic algorithm (GA) is proposed and ANOVA is used to fine tune the parameter setting of GA. The experiment shows that the proposed approach is more effective to find the near-optimal schedule than the simulated annealing algorithm for both small-size problem and large-size problem.

In this paper, a multi-level genetic algorithm is proposed to minimize the makespan for the re-entrant flow shop scheduling problem (RFSP) with dual resource constraints. In the re-entrant flow shop, routes of all jobs are identical, while some jobs will visit certain machines more than once at different stages of processing. The number of the re-entrant jobs and the re-entrant frequency may increase or decrease based on the manufacturing or repair process of different products. Each workstation consists of several machines and operators, which is regarded as resource constraints. A typical example of the re-entrant manufacturing system is the semi-conductor manufacturing process, especially wafer fabrication line. In the semiconductor line, chemical material is added to the silicon wafers layer by layer where the wafer needs to repeatedly go through the clean rooms, depending on the manufacturing procedure of the wafer. Another example is the maintenances industry where repair parts will iteratively go through typical operations such as inspection, blasting, welding, grinding, fitting, coating, and packing. Moreover, depending on the repairing technology and product specification, the required production capacity and time would be different. Therefore, an extensive study on re-entrant flow shop is essential for balancing the production efficiency and product quality. According to Tseng and Chen (2009), a mode is the combination of different resources and/or levels of resource requirements with a specified duration. For many scheduling problems, machines and skilled labor requirements vary at different workstations. The selection of the execution mode will directly influence the production duration and product quality. Therefore, it is critical to determine the execution mode for each task. Take the electro-coating as an example, sophisticated machines such as high pressure sprayer have high performance but consume more paint and less prone to rework, while skilled worker may use less paint but more time for the same job and has a higher chance of rework. Hence, different modes of production (i.e. machine or man) will affect rework probability. Therefore, effective scheduling of high cost labor and machine can provide a higher payoff for enterprises. The re-entrant flow shop scheduling problem considered here is based on a maintenance company that offers repair, modification and upgrading services for a wide range of machinery from marine, electrical to mechanical. The repair parts include huge parts such as buckets, fuel nozzles, power nozzles, shroud, and rotors. Approximately 95% of repair parts of this company need to go through the blasting, heat treating, welding, alloying, grinding, and inspection procedures. If parts fail in the inspection process or new faults are found, the repair parts need to be returned to the previous workstations and reworked. As long as rework happens, the due dates of the re-entrant jobs are becoming tighter. Moreover, as the repairing execution mode is optional, the corresponding technology and standard will differ. Thus the machine time and required operators will vary. The re-entrant probability and the number of re-entrant jobs will change accordingly. Take the power nozzles repairing procedure as an example. According to different repairing technologies, a power nozzle part can be repaired in a complicated mode which goes through 40 steps. Under this mode, a typical piece of power nozzle will cost 400 units of worker time, 120 units of machine time with 9% of rework possibility. Or when the job is urgent, the same piece of power nozzle can be done by applying the compact mode that only goes through 13 steps, consuming 215 units of worker time, 420 units of machine time with as high as 15% of chance to be reworked. No matter it is the original job or the re-entrant job, the differences of the execution modes are the processing time at some particular stages and the consumption of the machine and manpower resources. Some of the parts do not need to pass all the machines. Similar phenomena can be found from the coating procedure. High pressure sprayers have good performance but consume more paint and less prone to be reworked, while skilled worker may use less paint but more time for the same job and has a higher chance of rework. Therefore, the choice of execution mode can affect the overall makespan. Prior to the problem formulation and proposed method, we will review the related literature in Section 2. Section 3 will formulate the problem and Section 4 elaborates the multi-level encoding genetic algorithm with various operators setting. In Section 5, we describe the experiment and analyze the corresponding results. In Section 6, the main explanation of the experimental results is further discussed and finally Section 7 summarizes the paper and draws conclusions based on our experimental results.

Efficient design of the re-entrant flow shop scheduling is critical for those semi-conductor industries or repairing companies when facing the resource constraints. Several approaches have been proposed for this problem, most of which ignore the dependency between the re-entrant possibility and execution mode selection. In this paper, we have presented a multi-level GA-based approach for balancing the rework percentage and causing higher resource consumption. In this approach, the multi-level encoding keeps the intact information. On the other hand, fastening the convergence of solution is crucial because the execution mode selection and job scheduling are integrated and optimized together. Experimental results on small problem instances have demonstrated the good performance and consistency of the proposed approach when compared with simulated annealing algorithm. Furthermore a series of experiments have been carried out to determine the most influenced factor for the GA and the best combination of parameters have been examined. Based on the fine-tuned parameters, large problem size testes are executed and GA shows superiority over SA. The contribution of this paper is the presentation of a robust multi-level encoding genetic algorithm for resource-constrained re-entrant scheduling problem in the flow shop. The approach is customizable and flexible so as to provide significant potential for extension to other constrained optimization problems.