الگوریتم تکاملی ترکیبی برای زمانبندی کار تحت تعمیر و نگهداری ماشین آلات

The job scheduling problem (JSP) belongs to the well-known combinatorial optimization domain. After scheduling, if a machine maintenance issue affects the scheduled processing of jobs, the delivery of jobs must be delayed. In this paper, we have first proposed a Hybrid Evolutionary Algorithm (HyEA) for solving JSPs. We have then analyzed the effect of machine maintenance, whether preventive or breakdown, on the job scheduling. For the breakdown maintenance case, it is required to revise the algorithm to incorporate a rescheduling option after the breakdown occurs. The algorithm has been tested by solving a number of benchmark problems and thence comparing them with the existing algorithms. The experimental results provide a better understanding of job scheduling and the necessary rescheduling operations under process interruption.

Job scheduling is a well-known task in the manufacturing industry. In this paper, we consider Job Scheduling Problems (JSPs) with n jobs and m machines that involve active constraints such as machine capacity and precedence requirements. It is considered that a machine can only perform a particular type of operation. Thus, a machine is able to execute just a single operation of a job. The operations are non-preemptive; an operation can neither be paused nor resumed after it is started. The execution time for each operation is known. The setup time or cost is assumed to be negligible. An operation can only be started if the preceding operations of the same job are complete. This description is similar to traditional job-shop scheduling problems [1] and [2]. Although a considerable amount of research has been carried out on how to develop effective solution approaches for JSPs, no single algorithm is well-accepted for all kinds of JSPs [3]. The deterministic scheduling algorithms that converge to the optimal solution are suitable for small-scale problems. They are, however, incapable of handling complex and large-scale problems. In contrast, the stochastic and heuristic algorithms can handle large-scale problems, and provide near optimal solutions with a small computational effort [4]. As a result, these algorithms are popular when solving complex and large-scale scheduling problems. In almost all research on JSPs, schedules are produced under ideal conditions, assuming there will be no disruptions of any type. However, machine unavailability is a common event on the shop floor due to both preventive and breakdown maintenance of machineries and their supporting equipments [4]. The inclusion of such unavailability of processing resources with the JSPs makes the resulting problem not only more practical, but also more complex and challenging. The preventive maintenance schedules, which are usually known in advance, can easily be incorporated in generating a job scheduling. However, in the case of sudden machine failure, the operations scheduled on the broken machine cannot be resumed until the machine is either appropriately repaired or replaced by a new one. During and after the machine repair/replacement, the continued implementation of the schedule generated earlier would delay the completion of some jobs due to active precedence constraints. In order to minimize the delay, it is very important to re-optimize the remaining operations at the time of machine breakdown. Even after re-optimization, it is expected that there will be some delay in the completion of some or all jobs. In this research, we have proposed a Hybrid Evolutionary Algorithm (HyEA) for solving JSPs, that combines a genetic algorithm with a local search heuristic technique. We have considered makespan minimization as the fitness measure, as it is widely used in job scheduling problems. The total time between the starting of the first operation and the ending of the last operation is termed as the makespan. For a candidate solution, the local search heuristic technique identifies any gap left between any two consecutive operations (/jobs) on a machine. A job from the right of the gap can then be placed in it, if the gap is big enough for the operation without violating any precedence constraints. In addition, the job can also be placed in the gap, even if the gap is not big enough, but within a certain tolerance limit of the operation time, if it improves the overall fitness value. In this case it may need to shift other jobs to the right. We have extended this algorithm to study JSPs under sudden machine breakdowns. In the case of machine breakdown, the breakdown information is known after the actual breakdown, in fact, when the schedule is under implementation. In such a case, it is necessary to re-optimize the remaining operations by taking into account the machine downtime. We have solved 40 benchmark test problems using HyEA and have experimented by varying the tolerance limit for the local search heuristic. We have shown that the inclusion of the heuristic not only improves the performance of the EAs, but also reduces the overall computational requirements. To study JSPs with machine maintenance, we have chosen a manufacturing shop with ten machines. For experimentation, we have used probability distributions to generate the breakdown scenarios. We have found that the revised solution is able to recover from most of the breakdowns, regardless of when they occur. The novelties of our research presented in this paper can be summarized as follows. Although there exist a number of approaches for solving JSPs, no single algorithm is well-accepted for all kinds of JSPs. So there is a scope to develop new efficient algorithms. So our first goal was to develop a new Hybrid Evolutionary Algorithm (HyEA) that provides effective solutions for JSPs. Secondly almost all researches in JSPs dealt with the problem under ideal condition. However the real life situation faces many different disruptions. So we extended our study to deal with the disruption cases when the job processing is underway according to the job scheduling solution. This is a novel concept that would improve the efficiency in many manufacturing industry. Finally, the solution approach proposed in this research does not solve the corresponding mathematical model of the problem. Instead it considers the solution vector and the constraints from the problem description directly. The paper is organized as follows. After the introduction, a brief outline of a standard job scheduling problem with and without disruption is given. The evolutionary algorithm to solve JSPs is discussed in Section 3. Section 4 provides an experimental study for JSPs with and without random machine breakdowns. Finally, conclusions are given in Section 5.

The JSP is a well-known combinatorial optimization problem. A considerable amount of research has already been carried out to improve the algorithms for solving JSPs. Some of these algorithms are designed for specific cases of these problems, but still no algorithm guarantees optimality for all JSPs. In this paper, we have introduced a Hybrid Evolutionary Algorithm (HyEA) that provides better solutions for JSPs than many existing algorithms. As compared to GA alone, we have shown that HyEA not only improves the performance of GA, but also reduces the overall computational requirements. In almost all research on JSPs, the schedules were produced under ideal conditions, assuming that there will be no interruptions of any type. We have extended our algorithm to study JSPs under sudden machine breakdowns, where the breakdown information is known after the actual breakdown. We have solved and experimented with 20 benchmark test problems. For the condition of machine breakdowns, we have used different distributions to generate a number of breakdown scenarios. The experimental results show, that the re-optimization process carried out by our algorithm, is much more efficient than the existing practices.