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

This paper investigates an extended problem of job shop scheduling to minimize the total completion time. With aim of actualization of the scheduling problems, many researchers have recently considered realistic assumptions in their problems. Two of the most applied assumptions are to consider sequence-dependent setup times and machine availability constraints (MACs). In this paper, we deal with a specific case of MACs caused by preventive maintenance (PM) operations. Contrary to the previous papers considering fixed or/and conservative policies, we consider flexible PM operations, in which PM operations may be postponed or expedited as required. A simple technique is employed to schedule production jobs along with the flexible MACs caused by PM. To solve the given problem, we present a novel meta-heuristic method based on the artificial immune algorithm (AIA) incorporating some advanced features. For further enhancement, the proposed AIA is hybridized with a simple and fast simulated annealing (SA). To evaluate the proposed algorithms, we compare our proposed AIA with three well-known algorithms taken from the literature. Finally, we find that the proposed AIA outperforms other algorithms.

Job shop scheduling is one the most important scheduling environment taking place in many industrial setting. A job shop can be defined as follows: we have a set of n jobs that need to be processed on a set of m machines. Contrary to flow shops in which all the jobs have a same processing route, in job shops, it is assumed that each job j may have a unique processing route to meet the machines where Oij denotes i-th machine that job j must be processed on. Each job can be processed by only one machine at a time and each machine can process only one job at a time. We consider a non-preemptive case meaning that the processing of a job cannot be interrupted. The buffer between every two machines is unlimited meaning that a job can wait limitlessly for a machine if that machine is occupied. The aim is to find the job sequence on each machine in order to optimize the objective(s). The most frequently used objectives are the minimization of the makespan, maximum tardiness, total completion time, and total tardiness. The makespan and total completion time are manufacturer-oriented objectives while the maximum tardiness and total tardiness are costumer-oriented. In this paper, we intend to minimize the total completion time since it is regarded as a more realistic case of the makespan (Ruiz, Garica-Diaz, & Maroto, 2007). Since job shops belong to a specific class of combinatorial optimization problems known to be NP-hard ones (Cheung and Zhou, 2001), the presentation of metaheuristics is inevitable (Cheung and Zhou, 2001 and Zhou et al., 2006). On the one hand, machine setup time is a significant factor for production scheduling in all flow patterns manufacturing environments (Ruiz, Maroto, & Alcaraz, 2005). Setups are usually performed between two consecutive jobs on the same machine. These setups are either sequence-independent or dependent setup times (SDST) (Monma & Potts, 1989). As general, sequence-independent setup times can be ignored or combined with the processing times. In many real-life situations, such as color procedure in plastic industry, wafer testing in semiconductor manufacturing, the setup operations, such as cleaning up or changing tools, are not only often required between jobs but they are also strongly dependent on the immediately preceding process on the same machine (Pinedo, 1995 and Sule, 1996). The main reason why researchers have been motivated to use this assumption is to solve scheduling problems in a real manner and also because of the tremendous savings when setup times are explicitly included in scheduling decisions. In addition, we assume that setup is non-anticipatory meaning that the setup can be only started as soon as the machine and the job are both available. On the other hand, most papers dealing with scheduling problems assume that machines are always available during the scheduling period. However, in most real-life industrial cases, a machine can be unavailable for many reasons, such as unforeseen breakdowns (stochastic unavailability) or due to a scheduled preventive maintenance (PM) where the periods of unavailability are known in advance (i.e., deterministic unavailability). A breakdown makes the shop behavior hard to predict, and thereby reduces the efficiency of the production system. Therefore, scheduling maintenance to reduce the breakdown rate is commonly recognized by the decision makers. It is known that maintenance plays an important role in many industries, such as semiconductor and plastic industry; hence, it should be carefully explored. A poor scheduling of maintenance may greatly reduce the shop performance (Ruiz et al., 2007). As a result, the presentation of techniques to integrate production and PM activities is a key issue in the field of scheduling. Almost all the papers in the literature consider fixed or/and conservative policies (i.e., the PM operation must be scheduled at exactly predetermined intervals). We herewith apply a flexible criterion to consider PM operations along with productions jobs to gain more effective schedule. The problem studied in this paper can be denoted as J/STsd/∑Cj using the three-field notations of Graham, Lawler, Lenstra, and Rinnooy Kan (1979) to describe scheduling problems. With reference to the above explanations, the aim of this paper is to propose a high performing algorithm for a realistic problem of job shops to minimize total completion times. To consider job shops with machine availability constraints (MACs), we employ a simple and flexible criterion to gain more effective schedule. In this paper, we apply a high performing meta-heuristic based on the concept of artificial immune algorithm (AIA). The reason to AIA’s ever-increasing popularity among researchers is its powerful global exploration capability (Zandieh, Fatemi Ghomi, & Moattar Husseini, 2006). We also further enhance our proposed AIA by the hybridizing it with a very simple and fast form of simulated annealing (SA). We investigate its potential on solving the problem studied here against the adaptations of the some well-known algorithms in the literature through a set of instances. The rest of the paper is organized as follows. The literature review of the problem is presented in Section 2. Section 3 describes how to consider flexile machine availability constraints into our problem. Section 4 introduces the proposed algorithms. Section 5 is devoted to the computational results. Finally, Section 6 gives some conclusions and future research.

This paper has dealt with job shops with sequence dependent setup times and flexible machine availability constraints under the minimization of the total completion time. A hybrid algorithm (AISA) was proposed to tackle the given problem. This algorithm is the combination of the artificial immune algorithm and simulated annealing to overcome their drawbacks. To evaluate the proposed hybrid algorithm, we have compared it with some existing algorithms as well as AIA. The computational results showed the outperformance of the AISA. We have examined the behaviors of the algorithms versus the number of jobs, and the results have shown that AISA keeps its robust performance in the different levels of the problem sizes. It is interesting to extend the AISA to other scheduling problems or to the studied problem in this paper with other objectives, such as total tardiness and number of tardy jobs. It is worthy working on some other realistic assumptions like transportation times or extending the work done here to other scheduling problems.