یک روش اکتشافی موثر برای مشکل برنامه ریزی تولید کارگاهی انعطاف پذیر با فعالیت های تعمیر و نگهداری

Most production scheduling problems, including the standard flexible job-shop scheduling problem (FJSP), assume that machines are continuously available. However, in most realistic situations, machines may become unavailable during certain periods due to preventive maintenance (PM). In this paper, a flexible job-shop scheduling problem with machine availability constraints is considered. Each machine is subject to preventive maintenance during the planning period and the starting times of maintenance activities are either flexible in a time window or fixed beforehand. Moreover, two cases of maintenance resource constraint are considered: sufficient maintenance resource available or only one maintenance resource available. To deal with this variant FJSP problem with maintenance activities, a filtered beam search (FBS) based heuristic algorithm is proposed. With a modified branching scheme, the machine availability constraint and maintenance resource constraint can be easily incorporated into the proposed algorithm. Simulation experiments are conducted on some representative problems. The results demonstrate that the proposed filtered beam search based heuristic algorithm is a viable and effective approach for the FJSP with maintenance activities.

Due to their importance both in the fields of manufacturing industries and operations research, production scheduling and maintenance planning have been received considerable attention both in academia and in industry. However, in practice, production scheduling and maintenance planning are typically made independently despite the implicit common goal of maximizing equipment productivity between them (Cassady and Kutanoglu, 2003 and Cassady and Kutanoglu, 2005). Production scheduling is to allocate a limited set of resources to a number of jobs with optimization of one or multiple system criteria over time, while taking various constraints into account. Most of them assume that machines are always available at constant speed. They either ignore equipment failure or treat it as a random event (Cassady & Kutanoglu, 2003). Although reactive scheduling (or rescheduling) considers response scheduling after machine breakdown, it does not consider the practical requirement of high reliability for some equipment (e.g., furnace in steel plant, thermal generating units in power system (Mohanta, Sadhu, & Chakrabarti, 2007)). Reactive scheduling does not radically improve the reliability of machines either. Moreover, too often rescheduling may make the production system into a kind of chaos, because rescheduling leads to rearrangement of supporting resources (e.g., personnel, spare parts, and material handling devices). Therefore, a more realistic scheduling model should consider the machine availability constraint. This helps reducing the frequency of rescheduling and improving the robustness. Maintenance activities, especially preventive maintenance (PM), can restore the reliability of machines before it goes to breakdown. However, on one hand, maintenance activities take time that could otherwise be used for production scheduling; on the other hand, industrial applications cannot ignore the forecasted maintenance operations on the machines (Mauguiere, Billaut, & Bouquard, 2005). Therefore, the problem of simultaneously scheduling production jobs and maintenance activities obtains great attentions in recent years. Preventive maintenance planning is usually generated in a maintenance system, like Computerized Maintenance Management Systems (CMMS) and Asset Management System (AMS). Preventive maintenance planning requires some pre-scheduled or reserved unavailability interval of machines. Therefore, production scheduling with maintenance activities is also treated as availability constraint of machines in the literature. Schmidt (2000) has reviewed most results related to deterministic scheduling problems with availability constraints published before 1998. After Schmidt’s work, many efforts are devoted to the production scheduling with maintenance activities in different machine environments with different job characteristics and different optimality criteria. In the single machine context, Graves and Lee (1999) considered the scheduling problem with semiresumable 1 jobs and two maintenance intervals of a fixed duration on a single machine to minimize either total weighted completion time or the maximum lateness. Cassady and Kutanoglu (2003) proposed an integrated model that simultaneously determines production scheduling and preventive maintenance for a single machine in terms of the total weighted tardiness of jobs. This model is further extended into a similar model in terms of total weighted completion time in Cassady and Kutanoglu (2005). Compared with the total enumeration procedure in Cassady and Kutanoglu, 2005 and Sortrakul et al., 2005 presented heuristics based on the genetic algorithm (GA) for the same model. The job characteristics considered in these three papers are resumableand non-preemptive for PM. Chen and Liao (2005) studied the deterministic and probabilistic models of a single machine problem with different maintenance situations and resumable jobs with respect to the minimization of number of tardy jobs. The research is employed into a textile company. Ji, He, and Cheng (2007) analyzed the worst-case ratio of the LPT (longest processing time) dispatching rule for a single machine scheduling problem with nonresumable jobs and several periodic maintenance in terms of makespan minimization. Chen (2008) presented two optimization models and a heuristic for a single machine scheduling problem with nonresumable jobs and with flexible and periodic maintenance to minimize the makespan. Chen (2009) proposed a heuristic based on Moore’s algorithm and a branch-and-bound (B&B) algorithm to a single machine problem with periodic maintenance and nonresumable jobs with respect to the minimization of number of tardy jobs. In the parallel machine context, Lee and Chen (2000) extended the work of Graves and Lee (1999) to parallel machines with nonresumable jobs to minimize total weighted completion time. Gharbi and Haouari (2005) considered the identical parallel-machine scheduling problem with availability restrictions for both jobs (release time and delivery time constraints) and machines. The objective is to minimize the makespan and they presented an exact branch-and-bound algorithm to solve this problem. With the objective of makespan minimization, Liao, Shyur, and Lin (2005) studied the two-parallel machine problem with only one machine unavailable for a fixed and known period. Both nonresumable and resumable cases are considered and the problem is solved with modified methods based on the Two-Machine Optimization (TMO) algorithm. Then, Lin and Liao (2007) extended the same problem to the case where each machine has a fixed and known unavailable period. Lee and Yu (2008) discussed a parallel-machine scheduling problem with the objectives of minimization of the expected sum of weighted completion times and the expected number of tardiness jobs, respectively. Both resumable and nonresumable cases are studied. Liao and Sheen (2008) analyzed the parallel-machine scheduling problem with machine availability and eligibility constraints while minimizing the makespan. The problem is formulated into a maximum flow problem and a binary search algorithm is proposed. Mellouli, Sadfi, Chu, and Kacem (2009) considered the identical parallel-machine scheduling problem with availability constraints and total completion time criterion. Three exact approaches (mixed integer linear programming based methods, a dynamic programming method and a branch-and-bound method) are proposed as well as some heuristics adapted from the Shortest Processing Time (SPT) rule. Because of their fundamental characteristic and simplicity, single machine and parallel-machine scheduling problems with availability constraints under different criteria have been extensively studied. Readers are referred to Ma, Chu, and Zuo (2010) for a relative comprehensive overview. Recently, scheduling problems with availability constraints in more complicated environments, such as flow shop, job-shop and hybrid environments, have being attracted more and more attentions. Allaoui and Artiba (2004) studied the scheduling problem in a hybrid flow shop with both resumable and nonresumable jobs and maintenance constraints to minimize flow time and due date based criteria. Setup, cleaning and transportation times are also considered. Three dispatching rules, a simulated annealing (SA) heuristic and a flexible simulation model are separately used to solve the problem. Aggoune (2004) addressed a flow shop with machine availability constraints to minimize the makespan. Two variants of the non-preemptive constraints are considered: the starting times of maintenance activities are either fixed or flexible. An algorithm based on GA and tabu search (TS) is applied to solve the problem. Mauguiere et al. (2005) presented a new job-shop scheduling problem with machine availability constraints. The jobs can be either resumable or nonresumable depending on the unavailability period. Kubzin and Strusevich (2006) studied both a two-machine open shop problem and a two-machine flow shop problem to minimize the makespan. Each machine is subject to preventive maintenance, and the length of each maintenance period depends on its starting time. Breit (2006) investigated a problem of scheduling n preemptive jobs in a two-machine flow shop where the first machine is not available for processing during a given time interval, with the minimization of makespan. Gao, Gen, and Sun (2006) considered a flexible job-shop scheduling problem (FJSP) with machine availability constraints. The periods of unavailability are non-fixed and flexible within an end-time window and have to be determined during the scheduling procedure. A hybrid genetic algorithm is proposed to solve the problem. Ruiz, Garcia-Diaz, and Maroto (2007) considered preventive maintenance and production scheduling in regular flow shops and six meta-heuristics are proposed with comparisons. The multi-purpose machine (MPM) scheduling problem with fixed machine availability constraints in a job-shop is studied in Zribi, Kamel, and Borne (2008). A two-phase heuristic method is proposed to solve the problem. In the first phase, a heuristic based on priority rules to solve the assignment problem is developed, which can be improved with a tabu search algorithm. In the second phase, a GA is presented to solve the sequencing problem. Yang, Hsu, and Kuo (2008) investigated a two-machine flow shop where maintenance activities with a constant time must be done after completing a fixed number of jobs at most. The objective is to find the optimal job combinations and the optimal job schedule to minimize the makespan. Naderi, Zandieh, and Ghomi (2009) investigated a job-shop scheduling problem with sequence-dependent set-up times and maintenance activities to minimize the makespan. Two meta-heuristics, simulated annealing (SA) and GA are used to solve the problem. Based on the previous works review mentioned above, two gains could be drawn. Firstly, most existing literature focus on the problem of integrating production scheduling with preventive maintenance activities in the context of single machine, parallel machine and flow shop (especially two-machine problems). There is much less literature in the flexible job-shop manufacturing environment. As mentioned above, Gao et al. (2006) studied the general flexible job-shop scheduling problem combined with maintenance and production. Zribi et al. (2008) considered the MPM job-shop scheduling problem with availability constraints, which is the same problem as that of Gao et al. (2006). The hybrid flow shop with availability constraints in Allaoui and Artiba (2004) is one special type of FJSP with maintenance activities. Chan, Chung, Chan, Finke, and Tiwari (2006) considered distributed flexible manufacturing system (FMS) scheduling problems subject to machine maintenance constraint, in which the maintenance time is related to the machine age. This also covers the FJSP with maintenance activities. However, as compared with the models of single machine, parallel machine and flow shop, studies dealing with the FJSP with maintenance activities are rather rare. The flexible job-shop extends the classical job-shop by overcoming the assumption of predetermining machine route and extends the classical parallel machines with multiple processing stages, to meet the real-world scenarios of production flexibility in a wide variety of products and faster production rates. The FJSP allows that a machine may be capable of performing more than one type of operation (Najib, Dauzere-Peres, & Zaidat, 2002). The FJSP at least reflects two practical scenarios such as flexible manufacturing systems (FMS) with multi-processor machines and scheduling of crane in port container terminals. The FJSP possesses two difficulties: how to assign each operation to one machine that is able to perform it (routing sub-problem) and how to determine starting times for each operation (sequencing sub-problem). Due to its significant theoretical and industrial importance, the FJSP has been explored to some extent in the literature since seminal work of Brandimarte (1993), such as Kacem et al., 2002a, Kacem et al., 2002b, Xia and Wu, 2005, Pezzella et al., 2008, Gao et al., 2008 and Wang et al., 2008. Combined with the scheduling of maintenance activities and the standard FJSP provides additional complexity and new problems (Gao et al., 2006). More importantly, the integration scheduling of maintenance activities in the context of flexible job-shop environment is much more practical. Hence, it deserves further exploration to extend its theoretical significance and to explore its managerial implication. Secondly, most existing literature consider the fixed machine availability constraint, that is, the starting time and the end time of maintenance activities are pre-determined in maintenance planning. However, in practice, preventive maintenance tasks would impose non-fixed availability constraints on the machine in that the starting time of these maintenance tasks is generally flexible (Gao et al., 2006). This means that the starting time of the unavailable periods is not known in advance and has to be determined within the given time window during the scheduling process. Currently, there is only a few works considered the non-fixed availability constraints, such as Graves and Lee, 1999, Aggoune, 2004, Kubzin and Strusevich, 2006 and Gao et al., 2006. Therefore, there is much room for further investigation. Moreover, the constraints of maintenance resources (e.g., maintenance personnel, spare parts) should be considered. In a single machine scheduling problem with maintenance tasks, there is no need to consider this constraint since there is no conflict between maintenance resources and maintenance requirement. However, the conflict exists in the environment with multiple machines, and when only one machine can be maintained at any given time due to the limitation of maintenance resources. Lee and Chen (2000) considered the constraints of maintenance resources in parallel-machines scheduling with maintenance activities. In the FJSP with maintenance tasks discussed in Gao et al. (2006), the maintenance resource is assumed to be sufficient and the case of limited maintenance resource is not considered. In this context, inspired by the work of Gao et al. (2006), and based on our previous work in FJSP (Wang et al., 2008), this paper proposes a heuristic based on the filtered beam search (FBS) algorithm to solve the flexible job-shop scheduling problem (FJSP) with the non-fixed and fixed machine availability constraints due to the preventive maintenance, while considering two cases of maintenance resources constraints: sufficient maintenance resources or only one maintenance resource. In the first case, sufficient maintenance resources are available so that more than one machine can be maintained simultaneously if necessary. In the second case, only one machine can be maintained at any given time. A modified FBS procedure is presented to easily incorporate the machine availability constraint and the maintenance resource constraint. The rest of the paper is organized as follows: Section 2 presents the formal description of the flexible job-shop scheduling problem with maintenance activities. Section 3 illustrates the specific FBS procedure for the problem under investigation. In Section 4, benchmarking examples are investigated with the proposed algorithm and comparisons are presented. In Section 5, conclusions are drawn and future work directions are given.

Production scheduling with machine availability constraints due to preventive maintenance has attracted more and more researchers, as the importance of applications is recognized. In this work, a scheduling problem with both fixed and non-fixed machine availability constraints due to maintenance activities is considered in the flexible job-shop manufacturing environment. Two cases of maintenance resources (i.e., unlimited maintenance resources and only one maintenance resource) are also considered. Thus, the extended flexible job-shop scheduling problem with maintenance activities is a much closer to the scheduling problems in realistic applications and possesses much more difficulties. A heuristic based on filtered beam search (FBS) algorithm is proposed to solve this variant flexible job-shop scheduling problem (FJSP) with maintenance activities and maintenance resources constraint. A modified branching scheme is provided to easily incorporate both machine availability constraints and maintenance resource constraints. In order to test the effectiveness and easiness of the proposed heuristic, two representative experimental examples extended from the standard FJSP benchmarking problems and a MPM job-shop scheduling problem with maintenance activities are tested. The results show that the proposed heuristic can obtain satisfactory solutions. For the future work, the problem of maintenance resources optimality for the FJSP problem considering preventive maintenance with nonresumable jobs and resumable jobs in terms of manufacturing cost related performance measurement will be further investigated. Moreover, current work still belongs to the deterministic scheduling with machine availability constraints, in which maintenance activities are given as problem input data, not as a result of the machine operation (e.g., a function of machining time). Future work will also concern the jointly optimization problem considering PM policy selection, PM operations scheduling and production scheduling.