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

The majority of the scheduling studies carry a common assumption that machines are available all the time. However, machines may not always be available in the scheduling period due to breakdown or preventive maintenance. Taking preventive maintenance activity into consideration, we dealt with the two-machine flowshop scheduling problem with makespan objective. The preventive maintenance policy in this paper was dependent on the number of finished jobs. The integer programming model was proposed. We combined two recent constructive heuristics, HI algorithm and H algorithm, with Johnson’s algorithm, and named the combined heuristic H&J algorithm. We also developed a constructive heuristic, HD, with time complexities O(n2). Based on the difference in job processing times on two machines, both H&J and HD showed good performance, and the latter was slightly better. The HD algorithm was able to obtain the optimality in 98.88% of cases. We also employed the branch and bound (B&B) algorithm to obtain the optimum. With a good upper bound and a modified lower bound, the proposed B&B algorithm performed significantly effectively.

Most studies on scheduling assume that machines are available throughout the planning horizon. However, in practice, machines are not always available (Pinedo, 2002). That is, machines may not be available during the scheduling horizon due to breakdown (stochastic) or preventive maintenance (deterministic). Taking preventive maintenance activity into consideration, we dealt with a flowshop scheduling problem with limited machine availability. In capital-intensive industry, production generally proceeds on a continuous basis and the availability of production centers at all time is very important. Nevertheless, maintenance activities have to be performed. Possible events that necessitate maintenance operations include: (1) the occurrence of a failure (failure-based maintenance); (2) the elapse of a certain amount of time or usage (use-based maintenance); and (3) the tested condition of a unit (condition-based maintenance) (Art, Knapp, & Lawrence, 1998). For recent surveys of problems with limited machine availability, refer to Sanlaville and Schmidt, 1998 and Schmidt, 2000. However, research on these problems has started only recently. Johnson’s rule is well known for the case of continuous machine availability, making the problem of minimizing the makespan easy to solve for two machines. Lee (1997) proved the problem to be NP-hard when an interval of non-availability (or hole, for short) occurs, and then developed a pseudo-polynomial dynamic programming algorithm to optimally solve the problem. Lee presented two heuristic algorithms. The first heuristic had a worst-case error bound of 1/2 for the case in which the hole occurred on the first machine. The second heuristic with a worst-case error bound of 1/3 for the case in which the hole occurred on the second machine. Similarly, Cheng and Wang (2000) studied the problem with the holes occurred on the first machine. Their heuristic had a worst-case error bound of 1/3. Breit (2004), studying the holes occurring on the second machine, proposed a heuristic with a worst-case error bound of 1/4. Cheng and Wang (1999) considered a special case where the availability constraint is imposed on each machine, but the two availability constraints are consecutive. Lee (1999) considered the two-machine flowshop problem under the assumption that if a job cannot be finished before the next down period of a machine, then the job must be restarted partially when the machine becomes available again. His model was called semi-resumable. The model contained two important special cases: resumable where the job can be continued without any penalty and non-resumable where the job must be totally restarted. Lee also developed a pseudo-polynomial dynamic programming algorithm to optimally solve the problem and proposed heuristic algorithms with an error bound analysis. Blazewicz, Breit, Formanowicz, Kubiak, and Schmidt (2001) studied a two-machine flowshop problem where machines are unavailable in given time intervals. They analyzed two constructive heuristics, Johnson’s algorithm and look-ahead heuristic, and a heuristic based on simulated annealing (SA). Blazewicz et al. concluded that the SA-based heuristic is a more effective approach. Kubiak, Blazewicz, Formanowicz, Breit, and Schmidt (2002) proved that no polynomial time heuristic with a finite worst-case bound may exist when at least two holes are allowed to occur. Their study also showed that makespan minimization becomes NP-hard in the strong sense even if arbitrary number of holes occur on one machine only. Most important, Kubiak et al. proved two important properties of optimal schedules for the two-machine flowshop, a theory which serves as the framework of the current paper. They further developed a branch and bound algorithm based on the proposed properties. Some papers stated that machines are available in time windows, which is true in computer systems. Aggoune et al., 2001 and Aggoune, 2004 considered a flowshop problem with availability constraints, and provided two approaches to dealing with the maintenance activities: either starting time of the maintenance tasks are fixed or the maintenance tasks must be performed on a given time window. Aggoune et al. proposed a heuristic based on genetic algorithm to solve the makespan and the total weighted tardiness minimization problems. Aggoune developed a heuristic based on genetic algorithm and tabu search to solve the makespan minimization problem. Most studies on machine availability take into consideration the elapse of a certain amount of time or usage (use-based maintenance). However, Dell’Amico and Martello (2001) considered a practical assembly line for printed circuit boards. They asserted that the machine is not available after processing a fixed number of jobs to allow for time precision adjustment of the machines. That is, the time periods of preventive maintenance activities are dependent on the number of finished jobs. Liao, Chen, and Lin (2007) provided an algorithm to solve two parallel machines where there are one or more unavailability intervals for each machine. The algorithm had exponential time complexities, but it could optimally solve the various-sized problems in reasonable computation time. This paper dealt with the two-machine flowshop scheduling problem with makespan objective. The preventive maintenance policy was dependent on “the number of finished jobs”. We combined two recent constructive heuristics, HI algorithm (Cheng and Wang, 1999 and Cheng and Wang, 2000) and H algorithm (Breit, 2004), with Johnson’s algorithm, and named the heuristic H&J algorithm. We also developed a constructive heuristic, HD, which is based on the difference in the jobs’ processing times on two machines. In order to evaluate the performance of H&J and HD, we further developed a branch and bound algorithm with a modified lower bound. Compared with the optimum solution, H&J was able to obtain optimality in 1562 out of 1600 instances (97.63%), and HD was able to obtain optimality in 1582 out of 1600 instances (98.88%). Both H&J and HD showed good performance, and the latter was slightly better. The rest of the paper is organized as follows. Section 2 defines the terminology and constructs an integer programming model. Section 3 addresses basic properties of optimal solution and the development of two constructive heuristics, H&J and HD algorithms. A branch and bound algorithm (B&B algorithm) with a modified lower bound is constructed in Section 4. The performance of HD algorithm is evaluated in Section 5. The final section draws the conclusions of this work.

This paper has addressed a special case of a two-machine flowshop problem with availability constraints imposed on the first or/and the second machines. Moreover, we have developed a constructive heuristic, HD, which is based on the difference in processing times of job on two machines. We observe that the HD algorithm is slightly superior to H&J algorithm, which modifies HI algorithm and H algorithm. When holes only occur on M1, both the percentages of optimum of H&J and HD are 100%; when holes only occur on M2, the percentages of optimum of two heuristics are 98% and 100%, respectively. As holes occur on M1 and M2, the average percentages of obtaining the optimum of H&J and HD are 97.63% and 98.88%, respectively. The mean relative performances of H&J and HD according to the optimum, MR, are 0.0058% and 0.0017%, and the worst relative performances of H&J and HD according to the optimum, WR, are only 1.3100% and 0.2913%, respectively. The average computation time of HD is only 0.343 s for the 60-job instances. We may, therefore, conclude that the performance of the two heuristics is superior, especially the HD algorithm. HD is not only very close to the optimum but it obtains excellent efficiency. Also, the proposed modified lower bound of the B&B algorithm greatly contributes to the computation efficiency. For future research, it is interesting to develop a good heuristic for hybrid flowshop problem with various machine availability constraints.