Heuristic to Minimize the Number of Tardy Jobs for 2-Stages Assembly Scheduling Problem
Keywords:
Assembly Scheduling, Tardy Jobs, HeuristicAbstract
This research considers the assembly scheduling problem for a production process that consists of n jobs. The assembly system consists of 2 stages. In the first stage, there are m independent single machines that produce the components of a job, and when the components are finished, they are assembled into the work piece in the second stage. The research objective is to minimize the number of tardy jobs. The mathematical model is constructed to represent the problem characteristics and determine the optimal solution. Then, the solution procedure called heuristic Nattakorn, Witid, Tanawat, and Anot (NWTA) is developed based on the dispatching rule and the Moore-Hodgson Algorithm concept for determining a proper solution by considering tardy jobs and finding new positions to improve a production schedule. To evaluate the performance of the proposed heuristic, the solution obtained from the heuristic is compared with the optimal solution determined by the mathematical model and the solution found from the genetic algorithm. From the results of 30 problems, the heuristic NWTA can provide good solutions in a reasonable amount of time.
References
E.M. Morton, and D.W. Pentico, “Heuristic Scheduling System with Applications to Production System and Project Management,” John Wiley & Sons, Inc. New York, 1993.
J.M. Moore, “An n job, one machine sequencing algorithm for minimizing the number of late Jobs,” Management Science, vol.15, no.1, pp.102–109. 1968.
J. Cheriyan, R. Ravi, and M. Skutella, “A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs,” Operation Research Letters, vol.49, pp. 842-843. 2021.
J.Y. Lee and Y.D. Kim, “Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance,” Computer & Operations Research, vol. 39, pp. 2196-2205. 2021.
E. Molaee and G. Moslehi, “Minimizing the number of tardy jobs on a single machine with an availability constraint,” Journal of Industrial Engineering, vol.14, pp. 1-13. 2014.
W.-J. Chen, “Minimizing number of tardy jobs on a single machine subject to periodic maintenance,” Omega, vol. 37, no. 3, pp. 591–599, 2009.
A. Aydileka, H. Aydilek, and A. Allahverdi, “Algorithms for minimizing the number of tardy jobs for reducing production cost with uncertain processing times,” Applied Mathematical Modelling, vol. 45, pp. 982 – 996, 2017.
F. Ganji, and A. Jamali, “Minimizing the number of tardy jobs on single machine scheduling with flexible maintenance Time”, Journal of Algorithms and Computation, vol. 50, issue. 2, pp. 103 -119. 2018.
F.D. Croce, N.D. Gupta, and R. Tadei, “Minimizing tardy jobs in flow shop with common due date,” European Journal of Operational Research, vol. 120, pp. 375-381. 2000.
A.J. Ruiz-Torres, F.J. Lo´pez, J.C. Ho, “Scheduling uniform parallel machines subject to a secondary resource to minimize the number of tardy jobs,” European Journal of Operational Research, vol.179 pp. 302–315. 2007.
A. Najat, C. Yuan., S. Gursel., and Y. Tao, “Minimizing the Number of Tardy Jobs on Identical Parallel Machines Subject to Periodic Maintenance,” in Proceeding of 29th International Conference on Flexible Automation and Intelligent Manufacturing (FAIM2019), Limerick, Ireland, June 24-28, 2019, pp. 1409-1416.
F.S. Al-Anzi and A. Allahverdi, “Heuristics for a two-stage assembly flowshop with bicriteria of maximum lateness and makespan,” Computers & Operations Research, vol. 36, No. 9, pp. 2682-2689. 2009.
D. Terekhov, M.K. Dogru, U. Özen, and J. Christopher Beck,” Solving two-machine assembly scheduling problems with inventory constraints,” Computers & Industrial Engineering, Vol.63 (2012), pp.120-134, 2012.
A. Allahverdi, H. Aydilek, and A. Aydilek, “Two-stage assembly scheduling problem for minimizing total tardiness with setup times,” Applied Mathematical Modelling, Vol.40 (2016), pp. 7796-7815, 2016.
J.M. Framinan and P. Perez-Gonzalez,” The 2-stage assembly flowshop scheduling problem with total completion time: efficient constructive heuristic and metaheuristic,” Computers and Operations Research, vol.88 (2017), pp. 237-246, 2017.
A. Tozkapan, Ö. Kirca, and C.S. Chung, “A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem,” Computer and Operation Research, vol.30 (2), 309–320. 2003.
F.S. Al-Anzi and A. Allahverdi, “A hybrid tabu search heuristic for the two-stage assembly scheduling problem,” International Journal of Operations Research, vol. 3, no. 2, pp. 109–119. 2006.
F.S. Al-Anzi and A. Allahverdi, “An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time,” Journal of Manufacturing System, Vol. 32, no.4, pp. 825–830. 2013.
H. Kazemi, M.M. Mazdeh, and M. Rostami. “The two stage assembly flow-shop scheduling problem with batching and delivery,” Engineering Applications of Artificial Intelligence, vol.63 (2017), pp.98-107, 2017.
S.A. Basir, M,M. Mazdeh, and M. Namakshenas, “Bi-level genetic algorithms for a two-stage assembly flow-shop scheduling problem with batch delivery system,” Computers & Industrial Engineering, vol.126, pp.217-231, 2018.
I.S. Lee, “Minimizing total completion time in the assembly scheduling problem,” Engineering Applications of Artificial Intelligence, vol.122, pp. 211-218, 2018.
H. Ochia and O.B. Drissb, ”Scheduling the distributed assembly flowshop problem to minimize the makespan,” Procedia Computer Science, vol.164, pp.471-477, 2019.
S. Hatami, R. Ruiz, and C. Andres-Romano, “The distributed assembly permutation flowshop scheduling problem,” International Journal of Production Research, vol. 51, no. 17, pp. 5292-5308, 2013.
CN. Potts, SV. Sevast'janov, VA. Strusevich, LN. Van Wassenhove, and CM. Zwaneveld, “The two-stage assembly scheduling problem: complexity and approximation,” Operations Research, vol.43, no.2, pp. 346-355, 1995.
C.Y. Lee, T.C.E. Cheng, B.T.M. Lin, “Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem,” Management Science, vol.39, pp.616-625, 1993.
A. Allahverdi, FS. Al-Anzi, “Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize makespan with setup times,” International Journal of Production Research, vol.44, pp.4713-4735, 2006.
M. Pinedo,. “SCHEDULING: Theory, Algorithms, and Systems,” 4th edition. Prentice Hall, New Jersey, 2012.
K.R. Baker and D. Trietsch, “Principles of Sequencing and Scheduling”, John Wiley & Sons, Inc., Hoboken, New Jersey. Published simultaneously in Canada, 2009.
A. Chaimanee and W. Supithak “A memetic algorithm to minimize the total sum of earliness tardiness and sequence dependent setup costs for flow shop scheduling problems with job distinct due windows,” Songklanakarin Journal of Science and Technology, vol.40(5), pp.1203 1218, 2018.
C.Y. Lee and J.Y. Choi, “A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights,” Computers and Operations Researches, vol.22(8), pp.857-869, 1995.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
