Rescheduling of Parallel Machines under Machine Failures

Abstract:

In this study, we address a rescheduling problem in parallel machine environments under machines failures. To make a balance between efficiency and stability of the reschedules, we consider the total number of tardy jobs as efficiency measure and the number of jobs processed on different machines in the initial and revised schedules as a stability measure. Then a heuristic algorithm which synthesizes beam search (BS) and repair-based constraint satisfaction algorithm is developed. Numerical experiments are processed to evaluate the performance and efficiency of the proposed algorithm. The experimental results show that the proposed algorithm improves the results significantly.

• Periodical: Advanced Materials Research (Volumes 443-444)
• Pages: 724-730
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.443-444.724
• Online since: January 2012
• Authors: Chun Xia ShangGuan, Jun Tao Li, Rui Feng Shi
• Keywords: Beam Search, Machine Failures, Parallel Machine, Repair-Based Constraint Satisfaction Algorithm, Rescheduling

References

[1] J. C. Bean, J. R. Birge, J. Mittenthal, et al., Matchup scheduling with multiple resources, release dates and disruptions, Operations Research, vol. 39, 3, 1991, pp.470-483.

DOI: 10.1287/opre.39.3.470

[2] S. D. Wu, R. H. Storer, and P. C. Chang, One-machine rescheduling heuristics with efficiency and stability as criteria, Computers and Operations Research, vol. 20, 1, 1993, pp.1-14.

DOI: 10.1016/0305-0548(93)90091-v

[3] I. Sabuncuoglu and M. Bayiz, Analysis of reactive scheduling problems in a job shop environment, European Journal of Operational Research, vol. 126, 3, 2000, pp.567-586.

DOI: 10.1016/s0377-2217(99)00311-2

[4] C. Shangguan, H. Zhou, R. Shi, et al., Flow shop rescheduling problem and its improved repair-based constraint satisfaction algorithm, Computer Integrated Manufacturing Systems, vol. 14, 009, 2008, pp.1742-1751.

[5] M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Second edition ed. Upper Saddle, New Jersey: Prentice-Hall, (2002).

[6] T. E. Morton and D. W. Pentico, Heuristic Scheduling Systems: With Applications to Production Systems and Project Management: New York : Wiley-Interscience, (1993).

[7] B. Lowerre, The HARPY speech recognition system, Carnegie-Mellon University, Pittsburgh, (1976).

[8] C. Shangguan, H. Zhou, and R. Shi, Filtered Beam Search Algorithm with Partial Backtracking and Its Application to Job Shop Scheduling, Systems Engineering theory & Practice, vol. 27, 001, 2007, pp.143-151.

[9] I. Sabuncuoglu, Y. Gocgun, and E. Erel, Backtracking and exchange of information: Methods to enhance a beam search algorithm for assembly line scheduling, European Journal of Operational Research, vol. 186, 3, 2008, pp.915-930.

DOI: 10.1016/j.ejor.2007.02.024

[10] J. M. S. Valente, Beam search heuristics for the single machine early/tardy scheduling problem with no machine idle time, Computers & Industrial Engineering, vol. 55, 3, 2008, pp.663-675.

DOI: 10.1016/j.cie.2008.02.005

[11] E. Tsang, Foundations of constraint satisfaction. London: Academic press Limited, (1993).

[12] R. Dechter, Constraint processing. San Francisco: Morgan Kaufmann, (2003).

[13] S. Minton, M. Johnston, A. Philips, et al., Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence, vol. 58, 1-3, 1992, pp.161-205.

DOI: 10.1016/0004-3702(92)90007-k

[14] M. Tounsi and S. Ouis, An Iterative local-search framework for solving constraint satisfaction problem, Applied Soft Computing, vol. 8, 4, 2008, pp.1530-1535.

DOI: 10.1016/j.asoc.2007.12.006

[15] N. Yugami, Y. Ohta, and H. Hara, Improving repair-based constraint satisfaction methods by value propagation, 1994, pp.344-344.