JOB SHOP SCHEDULING CONSIDERING MAKESPAN, PENALTIES OF MACHINE IDLING, AND JOB OUT OF TIME
DOI:
https://doi.org/10.29121/granthaalayah.v7.i1.2019.1036Keywords:
JSS, Genetic, Algorithm, Multi-Objective OptimisationAbstract [English]
In this study, the job shop scheduling problem is analysed with respect to numerous objectives, and a multi-objective model is developed to optimise the makespan, maximum job earliness, maximum job tardiness, maximum machine idle time, total machine idling penalties, total job untimed penalties, and total penalties (multi-objective) using the genetic algorithm.
Downloads
References
S. French, "Sequencing and scheduling," An Introduction to the Mathematics of the Job-Shop, 1982.
J. Sridhar and C. Rajendran, "Scheduling in flowshop and cellular manufacturing systems with multiple objectives—a genetic algorithmic approach," Production Planning & Control, vol. 7, pp. 374-382, 1996. DOI: https://doi.org/10.1080/09537289608930365
B. Yagmahan and M. M. Yenisey, "A multi-objective ant colony system algorithm for flow shop scheduling problem," Expert Systems with Applications, vol. 37, pp. 1361-1368, 2010.
S. M. Johnson, "Optimal two‐and three‐stage production schedules with setup times included," Naval research logistics quarterly, vol. 1, pp. 61-68, 1954. DOI: https://doi.org/10.1002/nav.3800010110
V. R. Neppalli, C.-L. Chen, and J. N. Gupta, "Genetic algorithms for the two-stage bicriteria flowshop problem," European journal of operational research, vol. 95, pp. 356-373, 1996. DOI: https://doi.org/10.1016/0377-2217(95)00275-8
J. N. Gupta, "Designing a tabu search algorithm for the two-stage flow shop problem with secondary criterion," Production Planning & Control, vol. 10, pp. 251-265, 1999. DOI: https://doi.org/10.1080/095372899233217
J. N. Gupta, V. R. Neppalli, and F. Werner, "Minimizing total flow time in a two-machine flowshop problem with minimum makespan," International Journal of Production Economics, vol. 69, pp. 323-338, 2001. DOI: https://doi.org/10.1016/S0925-5273(00)00039-6
V. T'kindt, J. N. Gupta, and J.-C. Billaut, "Two-machine flowshop scheduling with a secondary criterion," Computers & Operations Research, vol. 30, pp. 505-526, 2003. DOI: https://doi.org/10.1016/S0305-0548(02)00021-7
G. Huang and A. Lim, "Fragmental optimization on the 2-machine bicriteria flowshop scheduling problem," in Tools with Artificial Intelligence, 2003. Proceedings. 15th IEEE International Conference on, 2003, p. 194.
A. Nagar, S. S. Heragu, and J. Haddock, "A branch-and-bound approach for a two-machine flowshop scheduling problem," Journal of the Operational Research Society, vol. 46, pp. 721-734, 1995. DOI: https://doi.org/10.1057/jors.1995.102
W.-C. Yeh, "A Memetic Algorithm for the n/2/Flowshop/α F+ β C max Scheduling Problem," The International Journal of Advanced Manufacturing Technology, vol. 20, pp. 464-473, 2002. DOI: https://doi.org/10.1007/s001700200179
C. Rajendran, "Heuristics for scheduling in flowshop with multiple objectives," European journal of operational research, vol. 82, pp. 540-555, 1995. DOI: https://doi.org/10.1016/0377-2217(93)E0212-G
J. M. Framinan, R. Leisten, and R. Ruiz-Usano, "Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation," European Journal of Operational Research, vol. 141, pp. 559-569, 2002. DOI: https://doi.org/10.1016/S0377-2217(01)00278-8
D. Ravindran, S. Selvakumar, R. Sivaraman, and A. N. Haq, "Flow shop scheduling with multiple objective of minimizing makespan and total flow time," The international journal of advanced manufacturing technology, vol. 25, pp. 1007-1012, 2005.
R. L. Daniels and R. J. Chambers, "Multiobjective flow‐shop scheduling," Naval Research Logistics (NRL), vol. 37, pp. 981-995, 1990. DOI: https://doi.org/10.1002/1520-6750(199012)37:6<981::AID-NAV3220370617>3.0.CO;2-H
H. Ishibuchi and T. Murata, "A multi-objective genetic local search algorithm and its application to flowshop scheduling," IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 28, pp. 392-403, 1998. DOI: https://doi.org/10.1109/5326.704576
P.-C. Chang, J.-C. Hsieh, and S.-G. Lin, "The development of gradual-priority weighting approach for the multi-objective flowshop scheduling problem," International Journal of Production Economics, vol. 79, pp. 171-183, 2002. DOI: https://doi.org/10.1016/S0925-5273(02)00141-X
T. Varadharajan and C. Rajendran, "A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs," European Journal of Operational Research, vol. 167, pp. 772-795, 2005. DOI: https://doi.org/10.1016/j.ejor.2004.07.020
T. Pasupathy, C. Rajendran, and R. Suresh, "A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs," The International Journal of Advanced Manufacturing Technology, vol. 27, pp. 804-815, 2006. DOI: https://doi.org/10.1007/s00170-004-2249-6
M. R. Garey, D. S. Johnson, and R. Sethi, "The complexity of flowshop and jobshop scheduling," Mathematics of operations research, vol. 1, pp. 117-129, 1976. DOI: https://doi.org/10.1287/moor.1.2.117
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.
K. R. Baker and B. Keller, "Solving the single-machine sequencing problem using integer programming," Computers & Industrial Engineering, vol. 59, pp. 730-735, 2010. DOI: https://doi.org/10.1016/j.cie.2010.07.028
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. DOI: https://doi.org/10.1007/BF02023076
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. DOI: https://doi.org/10.1016/j.asoc.2012.07.034
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. DOI: https://doi.org/10.1016/0360-8352(96)00047-2
Y. Wang, "A new hybrid genetic algorithm for job shop scheduling problem," Computers & Operations Research, vol. 39, pp. 2291-2299, 2012.
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. DOI: https://doi.org/10.1016/0377-2217(95)00012-F
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. DOI: https://doi.org/10.1504/IJMOR.2015.072274
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. DOI: https://doi.org/10.1016/j.cie.2006.09.002
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.
M. Al-Ashhab, "Multi-Objective Job Shop Scheduling Using a Lexicographic Procedure."
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.
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.
H. M. Wagner, "An integer linear‐programming model for machine scheduling," Naval Research Logistics (NRL), vol. 6, pp. 131-140, 1959. DOI: https://doi.org/10.1002/nav.3800060205
A. S. Manne, "On the job-shop scheduling problem," Operations Research, vol. 8, pp. 219-223, 1960. DOI: https://doi.org/10.1287/opre.8.2.219
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.
K. P. Yoon and C.-L. Hwang, Multiple attribute decision making: an introduction vol. 104: Sage publications, 1995.
N. Palisade, "Guide to Evolver–The genetic algorithm solver for Microsoft Excel," ed: Newfield, NY: Palisade Corporation, 1998.
Downloads
Published
How to Cite
Issue
Section
License
With the licence CC-BY, authors retain the copyright, allowing anyone to download, reuse, re-print, modify, distribute, and/or copy their contribution. The work must be properly attributed to its author.
It is not necessary to ask for further permission from the author or journal board.
This journal provides immediate open access to its content on the principle that making research freely available to the public supports a greater global exchange of knowledge.