Solving the Flexible Job Shop Scheduling Problem with Uniform Processing Time Uncertainty
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.
[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
<http://www.eil.utoronto.ca/profiles/chris/gz/uncertainty-survey.ps> or
<http://eil.utoronto.ca/profiles/chris/chris.papers.html>
[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.
[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
<http://www.eil.utoronto.ca/profiles/chris/gz/uncertainty-survey.ps> or
<http://eil.utoronto.ca/profiles/chris/chris.papers.html>
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:49740", author = "Nasr Al-Hinai and Tarek Y. ElMekkawy", title = "Solving the Flexible Job Shop Scheduling Problem with Uniform Processing Time Uncertainty", 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", volume = "6", number = "4", pages = "757-6", }
