الگوریتم ژنتیک با کنترل کننده فازی برای مشکلات برنامه ریزی تولید کارگاهی پیشگیرانه و غیر پیشگیرانه

In this paper, we propose a new genetic algorithm (GA) with fuzzy logic controller (FLC) for dealing with preemptive job-shop scheduling problems (p-JSP) and non-preemptive job-shop scheduling problems (np-JSP). The proposed algorithm considers the preemptive cases of activities among jobs under single machine scheduling problems. For these preemptive cases, we first use constraint programming and secondly develop a new gene representation method, a new crossover and mutation operators in the proposed algorithm. However, the proposed algorithm, as conventional GA, also has a weakness that takes so much time for the fine-tuning of genetic parameters. FLC can be used for regulating these parameters. In this paper, FLC is used to adaptively regulate the crossover ratio and the mutation ratio of the proposed algorithm. To prove the performance of the proposed FLC, we divide the proposed algorithm into two cases: the GA with the FLC (pro-fGA) and the GA without the FLC (pro-GA). In numerical examples, we apply the proposed algorithms to several job-shop scheduling problems and the results applied are analyzed and compared. Various experiments show that the results of pro-fGA outperform those of pro-GA.

This paper considers a preemptive case of activities among jobs in the job-shop scheduling problems (JSP). In preemptive job-shop scheduling problems (p-JSP), each job consists of a set of activities. Each activity is given an integer processing time and a machine on which it has to be processed. Activities can be interrupted at any time to let some other activities execute. There is no restriction on the number of interruptions, on the duration of an interruption or on the duration of a chunk. However, activities in non-preemptive job-shop scheduling problems (np-JSP) cannot be interrupted: Each activity must execute without interruption from its start time to its end time. Thus, if we consider both preemptive cases and non-preemptive cases in JSP, we have to use several different constraints for the preemptive cases compared with non-preemptive cases. The p-JSP has received a little attention from the academic and real-world community. Applegate and Cook (1991) implemented several computational studies for p-JSP and reported some benchmarks on preemptive cases and non-preemptive cases using 10 JSP. Baptiste (1995) considered resource constraints for p-JSP and np-JSP. He suggested some concepts of constraint programming for dealing with preemptive cases and compared with various p-JSP. Pape and Baptiste, 1994 and Pape and Baptiste, 1997 presented several constraint propagation techniques by constraint programming for p-JSP and np-JSP in constraint programming library. Baptiste (1999) considered an O (n4) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. However, p-JSP in the field of genetic algorithm (GA) has been received little attention by researchers. That is mainly because the method for representing P-JSP in GA is very difficult and it takes a lot of times to structure fine-tuning of GA parameters. For the fine-tuning of GA parameters, fuzzy logic controller (FLC) has been proved very useful. Most of researches using FLC can adaptively regulate the GA parameters (generation number, population size, crossover ratio, mutation ratio and others). Thus, much time for the fine-tuning of these parameters can be saved and the searching ability of GA in finding global optimum can be improved. Gen and Cheng (2000) suggested using FLC in GA fields. The pioneering work in extending the fuzzy logic technique to adaptive regulation of the strategy parameters of GA were those of Lee and Takagi, 1993, Xu and Vukovich, 1994 and Zeng and Rabenasolo, 1997. Zeng and Rabenasolo regulated crossover ratio, mutation ratio and crossover position of GA using FLC. These parameters are considered as the input variables of GA and also are taken into the output variables of the FLC. Wang, Wang, and Hu (1997) used two FLCs: one for the crossover ratio and the other one for the mutation rate. According to these contributions of FLC, recently GA has been more robustness than conventional GA. This paper focuses on developing an effective GA for solving both p-JSP and np-JSP in a single machine problem. The proposed algorithm considers some constraints developed by constraint programming for considering preemptive cases of activities among jobs and uses FLC for adaptively regulating GA parameters. In Section 2, the constraint programming for considering the preemptive case of activities are suggested and new mathematical formulations for both p-JSP and np-JSP are proposed. New concepts of GA for effectively representing both p-JSP and np-JSP are suggested in Section 3. The concepts of FLC for fine-tuning of GA parameters are considered in Section 4. The overall procedures of the proposed algorithm are proposed in Section 5. Numerical examples to demonstrate the effectiveness of the proposed algorithm are presented in Section 6 and conclusion follows in Section 7.

In this paper, we have proposed a new GA for applying p-JSP and in a single machine. The proposed algorithm np-JSP has used the concepts of constraint programming for considering preemptive and non-preemptive cases of activities among jobs. In the proposed algorithm, we have considered the chromosomes having various lengths to represent preemptive case of activities and used FLC to adaptively regulate crossover ratio and the mutation ratio of GA. To prove the ability of FLC, we have divided the proposed algorithm into two types: the GA with FLC (pro-fGA) and the GA without FLC (pro-GA). These two algorithms were analyzed and compared in numerical examples. The results applied have showed that pro-fGA is more effective than pro-GA in terms of the number of alternative schedules and CPU time as job size is increased. In the second examples, we have considered various situations increasing generation number and population size. The results applied have shown that pro-fGA has more effectiveness and robustness than pro-GA in terms of the best fitness, number of alternative schedules and CPU time.