الگوریتم های اکتشافی برای فروشگاه جریان دو دستگاه با در دسترس بودن دستگاه محدود

The paper studies a flowshop scheduling problem where machines are not available in given time intervals. The objective is to minimize the makespan. The problem is known to be NP-hard for two machines. We analyze constructive and local search based heuristic algorithms for the two-machine case. The algorithms are tested on easy and difficult test problems with up to 100 jobs and 10 intervals of non-availability. Computational results show that the algorithms perform well. For many problems an optimum solution is found.

The problem studied in this paper can be described as follows. Each of n jobs is to be processed on two machines M1 and M2 in this order. The processing times are given. Each machine may be unavailable for processing jobs in given time intervals which we call holes for convenience. At any time, each machine can process at most one job and each job can be processed on at most one machine. Preemption is allowed. The objective is to find a schedule which minimizes the maximum completion time Cmax. Fig. 1 shows a schedule for a problem instance with four jobs and three holes.In scheduling theory the basic model assumes that all machines are continuously available for processing throughout the planning horizon. This assumption might be justified in some cases but it does not apply if certain maintenance requirements, breakdowns or other constraints that cause the machines not to be available for processing have to be considered. This kind of constraints appear e.g. within MRP-II planning systems on a tactical level when a rolling horizon planning approach is used. Here, two consecutive time periods overlap where decisions taken in the first period constrain decisions for the second period. From this the problem arises that we have two sets of order requirements, one set having a fixed assignment to time intervals and the other being assigned to the remaining free processing intervals. The same kind of problem is repeated on the operational level of production scheduling. Here, some jobs are fixed in terms of starting and finishing times and resource allocation. When new jobs come in there are already jobs assigned to time intervals and corresponding machines while the new ones have to be processed using the remaining free processing intervals. Another application of limited machine availability comes from operating systems for mono- and multi-processors, where subprograms with higher priority will interfere with the current program executed. Numerous other examples exist where the investigation of limited machine availability is of great importance. This has also been proven by a growing market demand for software packages that can handle this feature of scheduling problems. For quite some time this type of scheduling problem has also attracted many researchers. For a recent survey of results on different kind of models refer to Sanlaville and Schmidt [1] and Schmidt [2]. However, research on flowshop problems with limited machine availability has started only recently. Since Johnson [3] and Garey et al. [4] it is well known for the case of continuous machine availability that the problem of minimizing the makespan is easy to solve for two machines (Johnson's rule) and that it becomes NP-hard for more than two machines. Lee [5] has shown that the problem gets more difficult if holes have to be considered. The problem already becomes NP-hard for two machines if there is a single hole on one machine only. In the same paper two approximation algorithms are presented, depending on the machine where the hole is located; one has a relative error of View the MathML source if the hole is on machine one, the other of View the MathML source if the hole is on machine two. Recently, Cheng and Wang [6] provided an improved approximation algorithm for the case with the hole on machine one; this algorithm has a relative error of View the MathML source. Lee [5] also proposes a dynamic programming algorithm for the case with one hole only. Kubiak et al. [7] prove that no polynomial time heuristic with a finite worst case bound can exist when there are at least two holes, provided that the later one occurs on machine two. They furthermore prove that makespan minimization becomes NP-hard in the strong sense even if an arbitrary number of holes occur on one machine only. On the other hand they show that there always exists an optimal schedule where the permutation of jobs scheduled between any two consecutive holes obeys Johnson's order. Due to these negative results in the same paper a branch and bound algorithm is given to solve the problem. The approach uses Johnson's rule for jobs scheduled between two consecutive holes. Taking into account that the branch and bound algorithm does not guarantee to find an optimal solution within a given time limit we want to analyze the performance of two constructive heuristics and one local search heuristic. The two constructive heuristics are Johnson's rule and a new look-ahead heuristic which is based on local optimization. From the variety of local search heuristics we choose simulated annealing because this method has proved to be very successful especially for solving flowshop scheduling problems [8], [9], [10] and [11]. In Section 2 we formulate the problem in greater detail. In Section 3 we present the heuristic algorithms we investigate. Section 4 describes the design of our experiment. The computational results are presented in Section 5. We finish with some conclusions.

We presented heuristic algorithms to solve the two-machine flowshop problem with limited machine availability. They were evaluated using easy and difficult problem instances. It turned out that at least 5870 out of 6000 easy instances and 41 out of 100 difficult instances could be solved to optimality using a combination of two constructive methods (Johnson's rule and a new look-ahead heuristic based on local optimization) and a simulated annealing algorithm. For 127 easy instances the optimality could not be proved. The time limit to achieve this result was roughly View the MathML source for each instance. The worst relative performance for easy and difficult instances was 2.6% and 44.4% above the optimum, respectively. At least 5812 out of 6000 easy instances and 13 out of 100 difficult instances could be solved combining the two constructive methods only with an average computation time of 0.33 and View the MathML source per instance, respectively. The heuristics proved to be robust with respect to relative shop and machine availability. The results suggest that the presented heuristic solution approach is a good alternative for solving large two-machine flowshop scheduling problems with limited machine availability. A next step in research could be to design heuristic algorithms for the m-machine flowshop scheduling problem with availability constraints.