American Journal of Industrial Engineering
ISSN (Print): 2377-4320 ISSN (Online): 2377-4339 Website: https://www.sciepub.com/journal/ajie Editor-in-chief: Ajay Verma
Open Access
Journal Browser
Go
American Journal of Industrial Engineering. 2019, 6(1), 1-12
DOI: 10.12691/ajie-6-1-1
Open AccessArticle

Multi-objective Job Shop Scheduling under Risk Using GA

Jaber S. Alzahrani1,

1Department of Industrial Engineering, Engineering College at Alqunfudah, Umm Al-Qura University, Saudi Arabia

Pub. Date: October 07, 2019

Cite this paper:
Jaber S. Alzahrani. Multi-objective Job Shop Scheduling under Risk Using GA. American Journal of Industrial Engineering. 2019; 6(1):1-12. doi: 10.12691/ajie-6-1-1

Abstract

In this study, a multi-objective job-shop scheduling model is developed to optimize makespan, maximum job tardiness and maximum and idle time of machines under risk. The model considers multi-jobs and multi-machines. Each task has a specific due date and random processing times of specific probability distribution. The model is solved using @RiskOptimizer.

Keywords:
job-shop scheduling optimization uncertainty @RiskOptimizer genetic algorithm

Creative CommonsThis work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Figures

Figure of 21

References:

[1]  G. Zhang, X. Shao, P. Li, and L. Gao, “An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem,” Computers & Industrial Engineering, vol. 56, pp. 1309-1318, 2009.
 
[2]  K.-L. Huang and C.-J. Liao, “Ant colony optimization combined with taboo search for the job shop scheduling problem,” Computers & operations research, vol. 35, pp. 1030-1046, 2008.
 
[3]  A. Udomsakdigool and V. Kachitvichyanukul, “Multiple colony ant algorithm for job-shop scheduling problem,” International Journal of Production Research, vol. 46, pp. 4155-4175, 2008.
 
[4]  M. S. Al-Ashhab, Munshi, S., Oreijah, M., & Ghulman, H., “Job Shop Scheduling Using Mixed Integer Programming,” International Journal Of Modern Engineering Research, vol. 7, p. 7, 2017.
 
[5]  K. R. Baker and B. Keller, “Solving the single-machine sequencing problem using integer programming,” Computers & Industrial Engineering, vol. 59, pp. 730-735, 2010.
 
[6]  M. Dell'Amico and M. Trubian, “Applying tabu search to the job-shop scheduling problem,” Annals of Operations research, vol. 41, pp. 231-252, 1993.
 
[7]  A. Ponsich and C. A. C. Coello, “A hybrid differential evolution—tabu search algorithm for the solution of job-shop scheduling problems,” Applied Soft Computing, vol. 13, pp. 462-474, 2013.
 
[8]  H. R. Lourenco, “Job-shop scheduling: Computational study of local search and large-step optimization methods,” European Journal of Operational Research, vol. 83, pp. 347-364, 1995.
 
[9]  M. Faccio, J. Ries, and N. Saggiorno, “Simulated annealing approach to solve dual resource constrained job shop scheduling problems: layout impact analysis on solution quality,” International Journal of Mathematics in Operational Research, vol. 7, pp. 609-629, 2015.
 
[10]  D. Sha and C.-Y. Hsu, “A hybrid particle swarm optimization for job shop scheduling problem,” Computers & Industrial Engineering, vol. 51, pp. 791-808, 2006.
 
[11]  T.-L. Lin, S.-J. Horng, T.-W. Kao, Y.-H. Chen, R.-S. Run, R.-J. Chen, et al., “An efficient job-shop scheduling algorithm based on particle swarm optimization,” Expert Systems with Applications, vol. 37, pp. 2629-2636, 2010.
 
[12]  L. Gao, G. Zhang, L. Zhang, and X. Li, “An efficient memetic algorithm for solving the job shop scheduling problem,” Computers & Industrial Engineering, vol. 60, pp. 699-705, 2011.
 
[13]  R. Cheng, M. Gen, and Y. Tsujimura, “A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation,” Computers & industrial engineering, vol. 30, pp. 983-997, 1996.
 
[14]  Y. Wang, “A new hybrid genetic algorithm for job shop scheduling problem,” Computers & Operations Research, vol. 39, pp. 2291-2299, 2012.
 
[15]  M. Al-Ashhab, “Multi-Objective Job Shop Scheduling Using a Lexicographic Procedure.”
 
[16]  P. Quanke, W. Ling, and G. Liang, “Differential evolution algorithm based on blocks on critical path for job shop scheduling problems,” Journal of Mechanical Engineering, vol. 46, pp. 182-188, 2010.
 
[17]  H. M. Wagner, “An integer linear‐programming model for machine scheduling,” Naval Research Logistics (NRL), vol. 6, pp. 131-140, 1959.
 
[18]  A. S. Manne, “On the job-shop scheduling problem,” Operations Research, vol. 8, pp. 219-223, 1960.
 
[19]  A. Scaria, K. George, and J. Sebastian, “An Artificial Bee Colony Approach for Multi-objective Job Shop Scheduling,” Procedia Technology, vol. 25, pp. 1030-1037, 2016.
 
[20]  K. P. Yoon and C.-L. Hwang, Multiple attribute decision making: an introduction vol. 104: Sage publications, 1995.
 
[21]  R. T. Marler and J. S. Arora, “Survey of multi-objective optimization methods for engineering,” Structural and multidisciplinary optimization, vol. 26, pp. 369-395, 2004.
 
[22]  R. L. Becerra and C. A. Coello Coello, “Epsilon-constraint with an efficient cultured differential evolution,” in Proceedings of the 9th annual conference companion on Genetic and evolutionary computation, 2007, pp. 2787-2794.
 
[23]  M. Laumanns, L. Thiele, and E. Zitzler, “An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method,” European Journal of Operational Research, vol. 169, pp. 932-942, 2006.
 
[24]  E. Zitzler, K. Deb, and L. Thiele, “Comparison of multiobjective evolutionary algorithms: Empirical results,” Evolutionary computation, vol. 8, pp. 173-195, 2000.
 
[25]  K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE transactions on evolutionary computation, vol. 6, pp. 182-197, 2002.
 
[26]  J.-F. Bérubé, M. Gendreau, and J.-Y. Potvin, “An exact ϵ-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits,” European journal of operational research, vol. 194, pp. 39-50, 2009.
 
[27]  M. Boulif and K. Atif, “An exact multiobjective epsilon-constraint approach for the manufacturing cell formation problem,” in Service systems and service management, 2006 International Conference on, 2006, pp. 883-888.
 
[28]  L. Grandinetti, F. Guerriero, D. Laganà, and O. Pisacane, “An optimization-based heuristic for the multi-objective undirected capacitated arc routing problem,” Computers & Operations Research, vol. 39, pp. 2300-2309, 2012.
 
[29]  M. Al-Ashhab, “Multi-Objective Job Shop Scheduling Using a Lexicographic Procedure,” International Journal of Engineering Science Invention (IJESI), vol. 7, p. 10, 2018.
 
[30]  D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. MA: Addison-Wesley, Reading, 1989.
 
[31]  D. Goldberg, “Genetic algorithms in search, optimization and Machine Learning Addison-Wesley Reading Google Scholar,” 1989.
 
[32]  D. Lei, “Simplified multi-objective genetic algorithms for stochastic job shop scheduling,” Applied Soft Computing, vol. 11, pp. 4991-4996, 2011.
 
[33]  J. Huang and G. A. Süer, “A dispatching rule-based genetic algorithm for multi-objective job shop scheduling using fuzzy satisfaction levels,” Computers & Industrial Engineering, vol. 86, pp. 29-42, 2015.
 
[34]  M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on evolutionary computation, vol. 1, pp. 53-66, 1997.
 
[35]  L. Ke, Q. Zhang, and R. Battiti, “MOEA/D-ACO: A multiobjective evolutionary algorithm using decomposition and antcolony,” IEEE transactions on cybernetics, vol. 43, pp. 1845-1859, 2013.
 
[36]  R. Kuo and W. Cheng, “Hybrid meta-heuristic algorithm for job shop scheduling with due date time window and release time,” The International Journal of Advanced Manufacturing Technology, vol. 67, pp. 59-71, 2013.
 
[37]  Z.-h. Jia, C. Wang, and J. Y.-T. Leung, “An ACO algorithm for makespan minimization in parallel batch machines with non-identical job sizes and incompatible job families,” Applied Soft Computing, vol. 38, pp. 395-404, 2016.
 
[38]  R. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,” in Micro Machine and Human Science, 1995. MHS'95., Proceedings of the Sixth International Symposium on, 1995, pp. 39-43.
 
[39]  H. Hirano and T. Yoshikawa, “A study on two-step search based on PSO to improve convergence and diversity for Many-Objective Optimization Problems,” in Evolutionary Computation (CEC), 2013 IEEE Congress on, 2013, pp. 1854-1859.
 
[40]  F. Zhao, J. Tang, and J. Wang, “An improved particle swarm optimization with decline disturbance index (DDPSO) for multi-objective job-shop scheduling problem,” Computers & Operations Research, vol. 45, pp. 38-50, 2014.
 
[41]  L.-L. Liu, R.-S. Hu, X.-P. Hu, G.-P. Zhao, and S. Wang, “A hybrid PSO-GA algorithm for job shop scheduling in machine tool production,” International Journal of Production Research, vol. 53, pp. 5755-5781, 2015.
 
[42]  K. Shahnaghi, H. Shahmoradi-Moghadam, A. Noroozi, and H. Mokhtari, “A robust modelling and optimisation framework for a batch processing flow shop production system in the presence of uncertainties,” International Journal of Computer Integrated Manufacturing, vol. 29, pp. 92-106, 2016.
 
[43]  M. Gong, T. Hou, B. Fu, and L. Jiao, “A non-dominated neighbor immune algorithm for community detection in networks,” in Proceedings of the 13th annual conference on Genetic and evolutionary computation, 2011, pp. 1627-1634.
 
[44]  M. Costa and E. Minisci, “MOPED: a multi-objective Parzen-based estimation of distribution algorithm for continuous problems,” in International Conference on Evolutionary Multi-Criterion Optimization, 2003, pp. 282-294.
 
[45]  Y. Gao, L. Peng, F. Li, M. Liu, and X. Hu, “Eda-based multi-objective optimization using preference order ranking and multivariate gaussian copula,” in International Symposium on Neural Networks, 2013, pp. 341-350.
 
[46]  L. Wang, S. Wang, and M. Liu, “A Pareto-based estimation of distribution algorithm for the multi-objective flexible job-shop scheduling problem,” International Journal of Production Research, vol. 51, pp. 3574-3592, 2013.
 
[47]  B. Liu, Y. Fan, and Y. Liu, “A fast estimation of distribution algorithm for dynamic fuzzy flexible job-shop scheduling problem,” Computers & Industrial Engineering, vol. 87, pp. 193-201, 2015.
 
[48]  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, vol. 2, pp. 129-147, 2004.
 
[49]  C. W. Wu, K. N. Brown, and J. C. Beck, “Scheduling with uncertain release dates,” AICS’05, p. 397, 2005.
 
[50]  A. Alhindi and Q. Zhang, “MOEA/D with Tabu search for multiobjective permutation flow shop scheduling problems,” in 2014 IEEE Congress on Evolutionary Computation (CEC), 2014, pp. 1155-1164.
 
[51]  P. C. Chang, S. H. Chen, Q. Zhang, and J. L. Lin, “MOEA/D for flowshop scheduling problems,” in 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), 2008, pp. 1433-1438.
 
[52]  J. S. Alzahrani, “JOB SHOP SCHEDULING CONSIDERING MAKESPAN, PENALTIES OF MACHINE IDLING, AND JOB OUT OF TIME,” International Journal of Research - Granthaalayah, vol. 7, p. 10, 2019.