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

In this paper, we deal with the Job-shop with Multi-Purpose Machine scheduling problem with Availability Constraints (JMPMAC). In the first part, we propose a heuristic, based on priority rules to solve the assignment problem. A local search algorithm is then introduced to improve this assignment solution. In the second part, we introduce a genetic algorithm to solve the sequencing problem. Finally, a new lower bound is developed for the problem to evaluate the quality of solutions.

In the scheduling literature, it is usually assumed that machines are available during the whole planning horizon. However, in many realistic situations, e.g. in typical industrial settings, machines may be unavailable for processing jobs after a breakdown or during a preventive maintenance activity. In fact, in manufacturing systems, machines are periodically submitted to reconfiguration, control or setup operations. The problem of job-shop with multi-purpose machines arises in the area of flexible manufacturing systems. Machines are equipped with different tools and called multi-purpose machines. A job can be processed on any machine equipped with the needed tool. Moreover, we assume that the machines are unavailable during given periods. We consider the deterministic model where the unavailability periods, corresponding to preventive maintenance tasks, are known in advance. We also assume that preemption of operations is not allowed. More precisely, an operation OijOij of job JiJi on machine MkMk starts only if its execution can be finished before MkMk becomes unavailable. The problem considered here is a generalization of the classical job-shop problem and the multi-purpose machine problem studied in Jurisch (1992), where machines are available all times. As compared to the literature dedicated to classical scheduling problems, studies dealing with limited machine scheduling problems are rather rare. Availability constraints have been firstly introduced in single machine (Adiri et al., 1989; Leon and Wu, 1992) and parallel machines (Schmidt, 1984 and Schmidt, 1988). Lee, 1996, Lee, 1997 and Lee, 1999 extensively investigated flow-shop scheduling problems with two machines. In particular, the author defined the resumable, non-resumable and semi-resumable models. An operation is called resumable if it can be interrupted by an unavailability period and completed without penalty as soon as the machine becomes available again. If the part of the operation that has been processed before the unavailability period must be partially (respectively, fully) re-executed, then the operation is called semi-resumable (respectively, non-resumable). Recently, flow-shop scheduling problems, with two machines and resumable jobs, have been treated in Blazewicz et al. (2001) and Kubiak et al. (2002). Besides, the job-shop problem under availability constraints has also been considered. Indeed, in Aggoune (2002) the author proposed a branch and bound algorithm with lower bound based on two-job decomposition for the job-shop problem with heads and tails and unavailability periods. However, to the best of our knowledge, the Job-shop with Multi-Purpose Machine scheduling problem with Availability Constraints (JMPMAC) has not been considered yet. The problem is strongly NP-hard since the problem without unavailability periods is already strongly NP-hard (Jurisch, 1992). Hence, in this paper we propose a heuristic method to solve this problem. The paper is organized as follows: the second section presents the specifications of the JMPMAC. In Section 3, we give a lower bound for the JMPMAC. Then in Section 4 we describe the assignment technique introduced to pre-optimize the makespan. In Section 5, we propose a genetic algorithm to solve the sequencing problem. Finally, numerical experiments and some conclusions concerning this research work are given.

In this paper, we have proposed a two-phase algorithm to deal with the JMPM with limited machine availability. We have shown that our approach gives interesting results compared with other types of methods as well as the theoretical lower bound presented here (Table 7). Table 7. JMPM example M1M1 M2M2 M3M3 M4M4 M5M5 O1,1O1,1 * 21 * * * J1J1 O1,2O1,2 * * 34 * * O1,3O1,3 * * 95 * 95 O1,4O1,4 53 53 * * * O1,5O1,5 55 * * 55 * O2,1O2,1 * * * 52 * J2J2 O2,2O2,2 * 16 * 16 16 O2,3O2,3 71 71 * * * O2,4O2,4 * 26 26 * 26 O2,5O2,5 21 * * * 21 O3,1O3,1 * 31 31 * * J3J3 O3,2O3,2 12 * * * 12 O3,3O3,3 42 42 * * * O3,4O3,4 * * * 39 * O3,5O3,5 * * * 98 98 O4,1O4,1 * * * 77 * J4J4 O4,2O4,2 * 77 * * * O4,3O4,3 79 * * 79 79 O4,4O4,4 55 * * 55 * O4,5O4,5 * * 66 66 66 O5,1O5,1 * * * * 37 J5J5 O5,2O5,2 * * 34 34 34 O5,3O5,3 64 * 64 * * O5,4O5,4 * 19 * * * O5,5O5,5 83 * * * * O6,1O6,1 * 43 43 * 43 J6J6 O6,2O6,2 * 54 * 54 54 O6,3O6,3 92 92 * * 92 O6,4O6,4 * * * 62 * O6,5O6,5 * 79 79 * 79 O7,1O7,1 93 * 93 * * J11J11 O7,2O7,2 * * * 69 * O7,3O7,3 * 87 87 87 * O7,4O7,4 * * 77 * 77 O7,5O7,5 * * 87 * * O8,1O8,1 60 * * * * J8J8 O8,2O8,2 41 41 * * * O8,3O8,3 38 * 38 * * O8,4O8,4 * 83 * * 83 O8,5O8,5 * * * 24 * O9,1O9,1 * * 98 98 * J9J9 O9,2O9,2 17 * * 17 * O9,3O9,3 * * * * 25 O9,4O9,4 44 * * * * O9,5O9,5 * 49 * 49 * O10,1O10,1 96 * 96 * * J10J10 O10,2O10,2 77 * * * 77 O10,3O10,3 * 79 * 79 * O10,4O10,4 75 75 * 75 * O10,5O10,5 * 43 43 * 43 O11,1O11,1 * * * * 28 J11J11 O11,2O11,2 * * 35 * * O11,3O11,3 95 * * * * O11,4O11,4 * * * 76 76 O11,5O11,5 * 7 * * * O12,1O12,1 61 * * * 61 J12J12 O12,2O12,2 * * 10 * 10 O12,3O12,3 95 95 95 * * O12,4O12,4 * 9 9 * * O12,5O12,5 * 35 * 35 * O13,1O13,1 * 59 * 59 59 J13J13 O13,2O13,2 16 * * 16 * O13,3O13,3 * 91 * * * O13,4O13,4 * * 59 * * O13,5O13,5 46 * 46 * 46 O14,1O14,1 43 * * * 43 J14J14 * 52 * * * * O11,3O11,3 28 * * * * O11,4O11,4 27 * 27 * 27 O11,5O11,5 * 50 * 50 * O15,1O15,1 87 * 87 * * J15J15 O15,2O15,2 * 45 * * * O15,3O15,3 * * 39 * * O15,4O15,4 9 9 * * 9 O15,5O15,5 * * * 41 * Table options As future research, we will apply this method on some benchmarks with practical data and extend the methods to the general flexible job-shop. We are also working on combined maintenance and production scheduling. We will look for optimizing two criteria, one for the production, the makespan, and one for the maintenance, the total cost.