برنامه ریزی مشکلات با فعالیت های نگهداری مختلف و شغل های غیر پیشگیرانه در دو دستگاه موازی یکسان
کد مقاله | سال انتشار | تعداد صفحات مقاله انگلیسی |
---|---|---|
21612 | 2010 | 8 صفحه PDF |
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : International Journal of Production Economics, Volume 124, Issue 1, March 2010, Pages 151–158
چکیده انگلیسی
This paper deals with the problem of processing a set of n jobs on two identical parallel machines. In order to reduce the probability of machine breakdown with minor sacrifices in production time, the machines cannot process the jobs consecutively, they need to be maintained regularly (here we assume that the largest consecutive working time for each machine cannot exceed an upper limit T ). Two scheduling models are considered. In the first model, the maintenance activities are performed periodically and the objective is to schedule the jobs on two machines such that the makespan is minimized. In the second model, the maintenance activities are determined jointly with the scheduling of jobs, and the objective is to minimize the total completion time of jobs. For the first problem, we introduce an O(n2)O(n2) time algorithm named MHFFDMHFFD and show that the performance ratio of MHFFDMHFFD is at most max{1.6+1.2σ,2}max{1.6+1.2σ,2}, where σ≜t/Tσ≜t/T, t is the amount of time to perform each maintenance activity. For the second problem, we apply the classical SPT algorithm to it and show that the worst-case bound of SPT algorithm is no more than 1+2σ1+2σ. We also point out that for the case of single machine, if the SPT schedule has three batches, then the upper bound of SPT algorithm can be reduced from the known result 21/17 to 11/9 under the assumption that t<Tt<T.
مقدمه انگلیسی
The majority of machine scheduling literature assumes that the machines are available for processing jobs at all times during the planning horizon. However, this assumption may not be valid in a real production situation due to preventive maintenance (a deterministic event) or breakdown of machines (a stochastic phenomenon). Uncertain breakdowns will make the shop behavior hard to predict, thus reducing the efficiency of the production system. Maintenance activity can reduce the breakdown rate with minor sacrifices in production time. The role and importance of industrial maintenance has increasingly been recognized by decision makers (Pinjala et al., 2006, Alsyouf, 2007, Alsyouf, 2009 and Dowlatshahi, 2008). Therefore, scheduling the maintenance in manufacturing systems has gradually become a common practice in many companies. However, according to practical experience, it sometimes can be found that some of the machines are awaiting maintenance while there are jobs waiting to be processed by these machines. This is due to the lack of coordination between maintenance planning and production scheduling. Therefore, there is a need to develop efficient scheduling methods to improve the situation by deriving a satisfactory schedule that considers both jobs and maintenance activities simultaneously. With proper planning of the maintenance activities, the shop can improve production efficiency and safety, resulting in increased productivity and heightened safety awareness (Art et al., 1998). The scheduling of maintenance activities can be determined either before the scheduling of jobs, or jointly with the scheduling of jobs. In the first case, the maintenance periods are known and fixed in advance. Thus the problem of scheduling jobs with this kind of maintenance reduces to the problem often referred in the literature as scheduling with machine availability constraints . Adiri et al. (1989), Lee and Liman (1992) and Makoto and Hiroshi (1999) studied a single machine problem with a machine availability constraint, respectively. Lee and Liman (1993) considered a two-parallel-machine problem where one machine has an availability constraint and the other can process the jobs continuously. Allaouia et al., 2006 and Allaouia et al., 2008 and Cheng and Wang (2000) studied a two machine flowshop scheduling problem with an availability constraints, respectively. Note that all of these results assume that there is only one unavailability or availability period for each machine. However, maintenance activity has been scheduled regularly, or periodically in many manufacturing systems. Recently, Liao and Chen (2003) studied a single machine scheduling problem with periodic maintenance for the objective of minimizing the maximum tardiness. They proposed a branch and bound algorithm to derive an optimal schedule and a heuristic algorithm to search the near-optimal solution for large-sized problems. In addition, Chen (2006) studied a total flow time minimization problem on single machine with periodic maintenance. Ji et al. (2007) studied the same scheduling model with the objective of minimizing the makespan. They showed that the worst-case ratio of the classical LPT algorithm is 2. Further they pointed that there is no polynomial approximation algorithm with worst-case bound less than 2 unless P=NPP=NP, so the LPT algorithm is the best possible algorithm. Little research has been done in the literature for the model of jointly scheduling maintenance activities and jobs. Lee and Chen (2000) studied a parallel machine scheduling problem where each machine must be maintained once during the planning horizon. Allaouia et al. (2008) studied a two-machine flow shop scheduling problem for the objective of minimizing the makespan. Qi et al. (1999) and Akturk et al., 1999, Akturk et al., 2003 and Akturk et al., 2004 considered single machine scheduling problems where the maintenance activities need to be scheduled jointly with jobs, respectively. Recently, Qi (2007) considered two scheduling problems with this kind of maintenance activity on single machine and analyzed the worst-case performance of the classical SPT and EDD algorithms, respectively. Xu et al. (2008) studied a parallel machine scheduling problem with almost periodic maintenance requirement to minimize the completion time of the last finished maintenance. They proposed a heuristics algorithm named BFD-LPT for this problem and showed that there is no polynomial time approximation algorithm with a worst-case bound less than 2 unless P=NPP=NP. To the best of our knowledge, there is no research on two parallel machines with periodic maintenance or jointly scheduled maintenance in the literature. Thus, in this paper, we study the problems of processing a set of n jobs on two identical parallel machines subject to these two types of maintenance. Two scheduling models are considered. In the first model, the maintenance activities are performed periodically and the objective is to schedule the jobs on two machines such that the makespan is minimized. In the second model, the maintenance activities are determined jointly with the scheduling of jobs, and the objective is to minimize the total completion time of jobs. The remainder of this paper is organized as follows. In the next section, we define the problems formally. In Section 3, we study the makespan minimization problem on two identical parallel machines subject to periodic maintenance. In Section 4, we study the total completion time minimization problem subject to jointly scheduled maintenance. Our focus is to design efficient heuristic algorithms for these two problems and analyze the performance ratio of the algorithms.
نتیجه گیری انگلیسی
The importance of machine maintenance has been gradually recognized by the decision makers. Therefore, it becomes a common practice to schedule maintenance periodically or approximate periodically in many manufacturing systems. In this paper, we study the scheduling problems with multiple maintenances and non-preemptive jobs on two identical parallel machines. For the makespan minimization problem with periodic maintenance, we introduced an O(n2)O(n2) time MHFFDMHFFD algorithm with a worst-case performance ratio at most max{1.6+1.2σ,2}max{1.6+1.2σ,2}, where σ≜t/Tσ≜t/T. For the total completion time minimization problem with jointly scheduled maintenance, we show that the classical SPT algorithm is an efficient algorithm with a worst-case bound no more than 1+2σ1+2σ. Especially, for the case of single machine, we prove that if an SPT schedule has three batches and t<Tt<T, then the worst-case bound is no more than 11/9, which is an improvement of the result in Qi (2007). It should also be noted that the bounds proposed in this paper are just the upper bounds of the algorithms. Our future research will be directed to the discussing of the tightness of the bounds or present more efficient algorithms for these problems.