Solving the Flexible Job Shop Scheduling Problem with Uniform Processing Time Uncertainty

Authors: Nasr Al-Hinai, Tarek Y. ElMekkawy

Abstract:

The performance of schedules released to a shop floor may greatly be affected by unexpected disruptions. Thus, this paper considers the flexible job shop scheduling problem when processing times of some operations are represented by a uniform distribution with given lower and upper bounds. The objective is to find a predictive schedule that can deal with this uncertainty. The paper compares two genetic approaches to obtain predictive schedule. To determine the performance of the predictive schedules obtained by both approaches, an experimental study is conducted on a number of benchmark problems.

Keywords: Genetic algorithm, met-heuristic, robust scheduling, uncertainty of processing times

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1328726

References:

[1] M. Sevaux, and K. Sörensen, "A genetic algorithm for robust schedules in a one-machine environment with ready times and due dates," Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 4OR 2, 2004, pp. 129-147.
[2] N. Al-Hinai, and T. ElMekkawy, "An efficient hybridized genetic algorithm architecture for the flexible job-shop scheduling problem," Flexible Services and Manufacturing Journal, vol. 23, 2011, pp. 64-85, doi: 10.1007/s10696-010-9067-y.
[3] R. L. Daniels, and P. Kouvelis, "Robust scheduling to hedge against processing time uncertainty in single-stage production," Management Science, vol. 41, no. 2, 1995, pp. 363-376.
[4] P. Kouvelis, R. L. Daniels, and G. Vairaktarakis, "Robust scheduling of a two-machine flow shop with uncertain processing times," IIE Transactions, vol. 32, 2000, pp. 421-432.
[5] R. H. Möhring, F. J. Radermacher, and G. Weiss, "Stochastic scheduling problems II: Set strategies," ZOR - Zeitschrift f├╝r Operations Research, vol. 29, 1985, pp. 65-104.
[6] R. Montemanni, "A mixed integer programming formulation for the total flow time single machine robust scheduling problem with interval data," Journal of Mathematical Modelling Algorithms, vol. 6, 2007, pp. 287-296.
[7] M. Pinedo, "On the computational complexity of stochastic scheduling problems," in Deterministic and stochastic scheduling, Dordrecht: Reidel, M. Dempster, J. Lenstra, and A. R. Kan (Eds.), 1982.
[8] C. W. Wu, K. N. Brown, and J. C. Beck, "Scheduling with uncertain durations: Modeling β-robust scheduling with constraints," Computers & Operations Research, vol. 36, 2009, pp. 2348-2356.
[9] Y. Xia, B. Chen, and J. Yue, "Job sequencing and due date assignment in a single machine shop with uncertain processing times," European Journal of Operational Research, vol. 184, 2008, pp. 63-75.
[10] U. M. Al-Turki, J. Mittenthal, and M. Raghavachari, "The singlemachine absolute-deviation early-tardy problem with random completion times," Naval Research Logistics, vol. 43, 1996, pp. 573- 587.
[11] X. Cai, and F. S. Tu, "Scheduling jobs with random processing times on a single machine subject to stochastic breakdowns to minimize earlytardy penalties," Naval Research Logistics, vol. 43, 1996, pp. 1127- 1146.
[12] L. Liu, H. Gu, and Y. Xi, "Robust and stable scheduling of a single machine with random machine breakdowns," International Journal of Advanced Manufacturing Technology, vol. 31, 2007, pp. 645-654.
[13] V. J. Leon, S. D. Wu, and R. H. Storer, "Robustness measures and robust scheduling for job shops," IIE Transactions, vol. 26, no. 5, 1994, pp. 32-43.
[14] S. R. Lawrence, and E. C. Sewell, "Heuristic, optimal, static, and dynamic schedules when processing times are uncertain," Journal of Operations Management, vol. 15, 1997, pp. 71-82.
[15] I. Sabuncuoglu, and S. Karabuk, "Rescheduling frequency in an FMS with uncertain processing times and unreliable machines," Journal of Manufacturing, vol. 18, no. 4, 1999, pp. 268-283.
[16] S. V. Mehta, and R. M. Uzsoy, "Predictable scheduling of a job shop subjected to breakdowns," IEEE Transactions on Robotics and Automation, vol. 14, no. 3, 1998, pp. 365-378.
[17] M. T. Jensen, “Improving Robustness and Flexibility of Tardiness and Total Flow-Time Job Shops Using Robustness Measure,” Applied Soft Computing; vol. 1, 2001, pp. 35-52.
[18] M. T. Jensen, “Generating robust and flexible job shop schedules using genetic algorithms,” IEEE Transactions on Evolutionary Computation, vol. 7, no. 3, 2003, pp. 275-288.
[19] D. C. Mattfeld, Evolutionary Search and the Job Shop, in Production and Logistics, Physica-Verlag, 1996.
[20] A. Anglani, A. Grieco, E. Guerriero, and R. Musmanno, “Robust scheduling of parallel machines with sequence-dependent set-up costs,” European Journal of Operational Research, vol. 161, 2005, pp. 704– 720.
[21] N. M. Matsveichuk, Yu. N. Sotskov, N. G. Egorova, and T. C. Lai, “Schedule execution for two-machine flow-shop with interval processing times,” Mathematical and Computers Modelling, vol. 49, 2009, pp. 991-1011.
[22] Z. Bouyahia, M. Bellalouna, P. Jaillet, and K. Ghedira, “A priori parallel machines scheduling,” Computers & Industrial Engineering, 2009, doi: 10.1016/j.cie.2009.11.009
[23] I. Mahdavi, B. Shirazi, and M. Solimanpur, “Development of a simulation-based decision support system for controlling stochastic flexible job shop manufacturing systems,” Simulation Modelling Practice and Theory, vol. 18, no. 6, 2010, pp. 768-786, doi: 10.1016/j.simpat.2010.01.015.
[24] A. J. Davenport, J. C. and Beck, “A survey of techniques for scheduling with uncertainty,” unpublished. Available online from or
[25] W. Herroelen, and R. Leus, “Project Scheduling under uncertainty: Survey and research potentials,” European Journal of Operational Research, vol. 165, 2005, pp. 289-306.
[26] H. Aytug, M. A. Lawley, K. McKay, S. Moha, and R. Uzsoy, “Executing production schedules in the face of uncertainties: A review and some future directions,” European Journal of Operational Research, vol. 161, 2005, pp. 86-110.
[27] J. Mula, R. Poler, J. P. García-Sabater, and F. C. Lario, “Models for production planning under uncertainty: A review,” International Journal of Production Economics, vol. 103, 2006, pp. 271-285.
[28] N. Al-Hinai, and T. Y. ElMekkawy, “Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm,” International Journal of Production Economics, vol. 132, 2011, pp. 279-291, doi: 10.1016/j.ijpe.2011.04.020.
[29] I. Kacem, S. Hammadi, and P. Brone, “Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems,” IEEE Transactions on Systems, Man and Cybernetics, vol. 32, no. 1, 2002, pp. 1-13.
[30] K. Sörensen, “Tabu searching for robust solutions,” in Proc.4th metaheuristics international conf., Porto, Portugal, 2001, pp. 707-712
[31] D. Y. Lee, and F. DiCesare, “Scheduling flexible manufacturing systems using petri nets and heuristic search,” IEEE Transactions on Robotics and Automation, vol. 10, no. 2, 1994, pp. 123 – 132.
[32] P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Annals of Operations Research, vol. 41, 1993, pp. 157–183.
[33] V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals,” Soviet Physics – Doklady, vol. 10, 1966, pp. 707-710.