بهینه سازی دو معیاری: به حداقل رساندن مقدار انتگرال و گسترش دهانه فازی مشکلات برنامه ریزی تولید کارگاهی

The processing times in reality are often uncertain and this uncertainty is critical for the scheduling procedures. This article presents bi-criteria genetic algorithm approach to solve fuzzy job shop scheduling problems (JSSPs), in which the integral value and the uncertainty of the fuzzy makespan (FM), which are conflicting objectives, are minimized. In this approach, imprecise processing times are modeled as triangular fuzzy numbers (TFNs), which results in a makespan that is a triangular fuzzy number. Therefore, it is practically important to pay attention to the uncertainty of the FM. Fuzzified benchmark problems; FT 6×6, La12, La13, and La14 were used to show the effectiveness of the proposed approach compared with optimizing fuzzy JSSPs with respect to either the FM or the uncertainty separately. A sensitivity analysis is also presented that shows the effect of the vagueness (uncertainty) of the processing times on the uncertainty of the FM.

Many researchers who deal with job shop scheduling problems (JSSPs) assume that time parameters, i.e. processing times, are fixed and deterministic. This assumption may be realistic if the operations under considerations are fully automated. However, whenever there is human interaction, this assumption may present difficulties in applying the schedule or even invalidating it. For example, the concept of processing time includes setup time and traveling between machines. Setup time and traveling time will not be exactly the same from day to day. Unfortunately, the uncertainty in these parameters has not received enough attention in [9], [10] and [11]. Recently, researchers start to address the uncertainty of the data in the real world (i.e. processing times, due dates) and use fuzzy numbers to address this uncertainty. The first significant application that considers the uncertainty in time parameters is the one of Fortemps [5]. In this application the author used six-point fuzzy numbers to represent fuzzy durations. He used simulated annealing (SA) as an optimization technique and the optimization criterion was to minimize the fuzzy makespan (FM). To test the approach, he fuzzified the FT 6×6 problem [4] and other famous problems such as La11, La12, La13, and La14 [13]. The produced solutions are flexible, since they are able to cope with all possible durations within the specified range. Chanas and Kasperski [2] considered fuzzy processing times and fuzzy due dates in the case of single machine scheduling problem. They show that Lawler’s algorithm can be applied fuzzy scheduling problems on a single machine. Sakawa and Kubota [15] presented a two-objective genetic algorithm to minimize the maximum fuzzy completion time and maximize the average agreement index. Ghrayeb [8] presented a genetic algorithm approach to optimizing fuzzy JSSPs, in which imprecise processing times are modeled as triangular fuzzy numbers (TFNs). This approach relies on using three-point fuzzy numbers to represent the imprecision in processing times. In that paper, the strength of his approach is that the produced schedule is flexible; it stays valid and can cope with all possible durations within the specified ranges. The objective (fitness) function considered was to minimizing the fuzzy makespan. However, the choice what objective function to use depends on the application environment. If the application is within an environment where time is costly, we may prefer to minimize the fuzzy makespan. On the hand, if the application is within a just-in-time environment, we may prefer to minimize the uncertainty of the makespan measured by its spread. That is, it is practically important to pay attention to the uncertainty of the fuzzy makespan. This uncertainty can be measured by the spread of the triangular fuzzy number that represents the fuzzy makespan as shown in Fig. 1. Full-size image (2 K) Fig. 1. Triangular fuzzy number A (a1, a2, a3). Figure options This article presents bi-criteria genetic algorithm approach to solve fuzzy JSSPs, in which the integral value and the uncertainty of the fuzzy makespan are minimized. In this approach, imprecise processing times are modeled as triangular fuzzy numbers, which results in a makespan that is modeled as a triangular fuzzy number.

In this article, we presented bi-criteria genetic algorithm approach to solve fuzzy job shop scheduling problems. Since processing times were modeled as triangular fuzzy numbers, the makespan is a triangular fuzzy number as well. Therefore, it is practically important to consider the uncertainty of the fuzzy makespan. This uncertainty is measured by the spread of the triangular fuzzy number that represents the fuzzy makespan. Minimizing the fuzzy makespan and the uncertainty (spread) are two conflicting objectives. The bi-criteria objective function introduces a solution by compromising between the two objectives. We realized that as we increase the weight of the spread in the objective function, we get higher makespan. But the results show that there is a range for the weight of the spread in the objective function where both the fuzzy makespan and the spread have acceptable value. It is worth mentioning here that as we introduced the spread to the objective function, more computation was required to obtain an optimal solution. The application environment may be the factor that decides how much weight to give to the spread in the objective function. If the application is within an environment where time is costly, we may prefer to give less weight to the spread. On the hand, if the application is within a just-in-time environment, for example, we may prefer to give more weight to the spread. Finally, the better estimate we can have for the processing times, the less uncertainty we get for the fuzzy makespan. As sensitivity analysis is presented to assess the effect of the uncertainty in processing times on the uncertainty (spread) of the fuzzy makespan.