Scheduling Optimization in Automotive Supplier Industry under Sequence Dependent Constraints

Abstract

In today's production conditions, it is very important for companies to produce products that meet the determined quality
standards. In addition to the production of semi-finished products produced in plastic injection lines with high quality and
efficiency, it is aimed to reduce the lost time and waste materials in production. Since automobile headlights can be in many
different colors, it is necessary to keep the product quality at a high level in the transition between colors in the production made
by plastic injection and to reduce the number of defective products caused by color errors. In this study, the problem of a single
row-dependent machine to reduce the amount of waste that occurs between color transitions in the plastic injection line of an
automotive side-industry company producing headlights is discussed. Tabu Search method, which is one of the heuristic
optimization algorithms was used to solve the problem. In the solution, production sequences that will reduce the amount of
waste of the products in the production program were created by using the annual data kept by the production department of the
factory. The algorithm was run using data from two machines out of 18, saving 134 kg of waste materials. It has been clarified
that if the developed algorithm is applied to all machines in the department, productivity and product quality will be increased
by saving waste materials.

Keywords

• sequence dependent setup time
• single machine scheduling
• Tabu Search

References

1. T. Saraç and S. Kaya, “Plasti̇k enjeksi̇yon maki̇neleri̇ni̇n vardi̇ya bazinda çi̇zelgelenmesi̇ problemi̇ i̇çi̇n bi̇r hedef programlama modeli̇,” Journal of Industrial Engineering, vol. 24, pp. 12–26.
2. T. Eren and E. Güner, “Sıra-Bağımlı Hazırlık Zamanlı İki Ölçütlü Çizelgeleme Problemi: Toplam Tamamlanma Zamanı Ve Maksimum Erken Bitirme,” Erciyes University Journal of Science and Technology, vol. 23, no. 1-2, pp. 95–105, 2007.
3. T. Eren, “Learning and Deteriorating Effects on the Single Machine Scheduling Problems,” International Journal of Engineering Research and Development, vol. 6, no. 1, pp. 15–20, Jan. 2014.
4. "Digital Conversion on the Way to Industry 4.0", Springer Science and Business Media LLC, 2021
5. Boasberg, James, The Department of Education, Tatarstan Academy, Russian Academy, Sciences Sibirsky Trakt, Geo Quinot, Sandra Liebenberg, et al. 2019. Duke Law Journal 1 (1): 1–13. https://doi.org/10.1017/CBO9781107415324.004.
6. Y. Zhao and G. Wang, “A dynamic differential evolution algorithm for the dynamic single-machine scheduling problem with sequence-dependent setup times Yue,” Journal of the Operational Research Society, vol. 71, no. 2, pp. 225–236, 2020.
7. M. Settar and T. Eren, “The Single Machine Scheduling Problem with Sequence-Dependent Setup Times and a Learning Effect on Processing Times.,” Applied Soft Computing Journal , vol. 71, pp. 291–306, 2018.
8. P. Perez-Gonzalez and J. M. Framinan, “Single machine scheduling with periodic machine availability,” Computers & Industrial Engineering, vol. 123, pp. 180–188, 2018.

9. R. M. Souza, S. Ricardo, and M. Felizardo, “Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties,” Computers and Operations Research, vol. 81, pp. 203–215, 2017.
10. Z. Ceylan, E. Karan, Ç. Bakırcı, and S. Sabuncu “Single Machine Scheduling Problem with Sequence Dependent Setup Times : An Application in White Goods I,” International Journal of Multidisciplinary Studies and Innovative Technologies, vol. 3, no. 1, pp. 14–21, 2019.
11. O. Herr and A. Goel, “Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints,” European Journal of Operational Research, vol. 248, no. 1, pp. 123–135, 2016.
12. T. Prabhakar, “A Production Scheduling Problem with Sequencing,” Management Science , vol. 21, no. 1, pp. 34–42, 2014.
13. Cheng, T. C.E., Wen Chiung Lee, and Chin Chia Wu.“Single-Machine Scheduling with Deteriorating Jobs and Past-Sequence-Dependent Setup Times.” Applied Mathematical Modelling 35 (4):1861–67,2011. https://doi.org/10.1016/j.apm.2010.10.015.
14. Wang, Ji Bo, and Jun Xiang Li. Single Machine Past-Sequence-Dependent Setup Times Scheduling with General Position-Dependent and Time-Dependent Learning Effects. Applied Mathematical Modelling 35 (3): 1388–95,2011. https://doi.org/10.1016/j.apm.2010.09.017.
15. K. Türker and Ç. Sel, “Sıra Bağımlı Hazırlık Operasyonları İçin Tek Ekipli Paralel Makinalarda Çizelgeleme Problemine Karma Yaklaşım,” J. Fac. Eng. Arch. Gazi Univ., vol. 26, no. 4, pp. 731–740, 2011.
16. C. Zhao and H. Tang, “Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs,” Computers & Industrial Engineering, vol. 59, no. 4, pp. 663–666, 2010.
17. J.-B. Wang, D. Wang, L.-Y. Wang, L. Lin, N. Yin, and W.-W. Wang, “Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times,” Computers & Mathematics with Applications, vol. 57, no. 1, pp. 9–16, 2009.
18. Biskup, Dirk, and Jan Herrmann. “Single-Machine Scheduling against Due Dates with Past-Sequence-Dependent Setup Times”, European Journal of Operational Research 191 (2): 587–92,2008. https://doi.org/10.1016/j.ejor.2007.08.028.
19. Karabati, S., and C. Akkan. “Minimizing Sum of Completion Times on a Single Machine with Sequence-Dependent Family Setup Times.” Journal of the Operational Research Society 57 (3): 271–80,2006. https://doi.org/10.1057/palgrave.jors.2601989.
20. Rabadi, G., Mollaghasemi, M., Anagnostopoulos, G.C. “A Branch-And-Bound Algorithm For The Early/Tardy Machine Scheduling Problem With A Common Due-Date And Sequence Dependent Setup Time,” Computers and Operations Research, 31, 1727–1751, 2004.
21. Gupta, Skylab R., and Jeffrey S. Smith. “Algorithms for Single Machine Total Tardiness Scheduling with Sequence Dependent Setups.” European Journal of Operational Research 175 (2): 722–39,2006. https://doi.org/10.1016/j.ejor.2005.05.018.
22. Armentano, Vinícius A., and Renata Mazzini. “A Genetic Algorithm for Scheduling on a Single Machine with Set-up Times and Due Dates.” Production Planning and Control 11 (7): 713–20, 2000. https://doi.org/10.1080/095372800432188.
23. Lee, Young Hoon, Kumar Bhaskaran, and Michael Pinedo. “A Heuristic to Minimize the Total Weighted Tardiness with Sequence-Dependent Setups.” IIE Transactions (Institute of Industrial Engineers) 29 (1): 45–52,1997. https://doi.org/10.1080/07408179708966311.
24. Tan, Keah Choon, and R. Narasimhan. “Minimizing Tardiness on a Single Processor with Sequence-Dependent Setup Times: A Simulated Annealing Approach.” Omega 25 (6): 619–34, 1997.https://doi.org/10.1016/S0305-0483(97)00024-8.
25. Rubin, Paul A., and Gary L. Ragatz. “Scheduling in a Sequence Dependent Setup Environment with Genetic Search.” Computers and Operations Research 22 (1): 85–99,1995. https://doi.org/10.1016/0305-0548(93)E0021-K.
26. H. J. Shin, C.-O. Kim, and S. S. Kim, “A Tabu Search Algorithm for Single Machine Scheduling with Release Times, Due Dates, and Sequence-Dependent Set-up Times,” The International Journal of Advanced Manufacturing Technology, vol. 19, no. 11, pp. 859–866, 2002.
27. Glover, F., “Tabu Search-Part I”, ORSA Journal on Computing, Cilt 1, No 3, 190-206, 1989.
28. Glover, F., “Tabu Search-Part II”, ORSA Journal on Computing, Cilt 2, No 1, 4-32 1990
29. S. Of et al., “Ham enerji̇ kaynaği kisitli termi̇k bi̇ri̇m i̇çeren si̇stemlerde çevresel ekonomi̇k güç dağıtımı probleminin çözümü,” no. 1, 2011.
30. F. Glover and M. Laguna, “Tabu Search,” Tabu Search, no. July, 1997, doi: 10.1007/978-1-4615-6089-0.
31. J. Xu, M. Sohoni, M. McCleery, and T. G. Bailey, “A dynamic neighborhood based tabu search algorithm for real-world flight instructor scheduling problems,” Eur. J. Oper. Res., vol. 169, no. 3, pp. 978–993, 2006, doi: 10.1016/j.ejor.2004.08.023.
32. A. M. Mohammed and S. O. Duffuaa, “A tabu search based algorithm for the optimal design of multi-objective multi-product supply chain networks,” Expert Syst. Appl., vol. 140, p. 112808, 2020, doi: 10.1016/j.eswa.2019.07.025.
33. A. Y. Abdelaziz, F. M. Mohamed, S. F. Mekhamer, and M. A. L. Badr, “Distribution system reconfiguration using a modified Tabu Search algorithm,” Electr. Power Syst. Res., vol. 80, no. 8, pp. 943–953, 2010, doi: 10.1016/j.epsr.2010.01.001.
34. Wan, Guohua, and Benjamin P.-C. Yen, “Tabu Search for Single Machine Scheduling with Distinct Due Windows and Weighted Earliness/Tardiness Penalties.,” European Journal ofOperational Research, vol. 142, no. 2, pp. 271–281, 2002.