International Journal of Applied Science and Engineering
Published by Chaoyang University of Technology

Chao-Tang Tseng*, Shu-Fu Zhang

Department of Industrial Engineering and Management, Chaoyang University of Technology, Taichung City 413310, Taiwan

 

Download Citation: |
Download PDF


ABSTRACT

The parallel machine scheduling problem with the consideration of GoS (grade of service) constraints originates from the service provision of different membership levels in the service industry. This scheduling problem has been widely found in industrial manufacturing and sustainable manufacturing practices. For example, in a sustainable manufacturing production line, multiple machines are set up as parallel machines to support each other to achieve shared manufacturing. However, the machines still have processing constraints with different service level constraints and do not support all jobs. This study investigates this parallel machine scheduling problem and uses the total completion time as the objective criterion. This criterion has not been studied in the literature for this scheduling problem. Several heuristics are proposed to solve the two-machine and multi-machine scheduling problems. The structure of these heuristics is mainly divided into two stages: the SPT rule and the insertion method. In addition, a fast method for calculating the total completion time is developed from the insertion method. The experimental results prove that the proposed heuristics are effective in solving this scheduling problem. For both small- and large-size problems, the proposed heuristics can obtain good solutions quickly and are potentially suitable for practical use.


Keywords: Eligibility constraints, Heuristic, Parallel machine, Scheduling, Total completion time.


Share this article with your colleagues

 


REFERENCES

  1. Akbar, M., Irohara, T. 2018. Scheduling for sustainable manufacturing: A review. Journal of Cleaner Production, 205, 866–833.

  2. Bektur, G., Saraç, T. 2019. A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server. Computers & Operations Research, 103, 46–63.

  3. Berthier, A., Yalaoui, A., Chehade, H., Yalaoui, F., Amodeo, L., Bouillot, C. 2022. Unrelated parallel machines scheduling with dependent setup times in textile industry. Computers & Industrial Engineering, 174, 108736.

  4. Conway, R.W., Maxwell, W.L., Miller, L.W. 1967. Theory of scheduling. Addison-Wesley Reading. Massachusetts. U.S.A.

  5. Epstein, L., Levin, A. 2011. Scheduling with processing set restrictions: PTAS results for several variants. International Journal of Production Economics, 133, 586–595.

  6. Glass, C.A., Kellerer, H. 2007. Parallel machine scheduling with job assignment restrictions. Naval Research Logistics, 54, 250–257.

  7. Huo, Y., Leung, J.Y.T., Wang, X. 2009. A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions. Discrete Optimization, 6, 292–298.

  8. Hwang, H.C., Chang, S.Y., Lee, K. 2004. Parallel machine scheduling under a grade of service provision. Computers & Operations Research, 31, 2055–2061.

  9. Ji, M., Cheng, T.C.E. 2008. An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan. Information Processing Letters, 108, 171–174.

  10. Ji, M., Ye, X., Qian, F., Cheng, T.C.E., Jiang, Y. 2022. Parallel-machine scheduling in shared manufacturing. Journal of Industrial and Management Optimization, 18, 681–691.

  11. Kusoncum, C., Sethanan, K., Pitakaso, R., Hartl, R.F. 2021. Heuristics with novel approaches for cyclical multiple parallel machine scheduling in sugarcane unloading systems. International Journal of Production Research, 59, 2479–2497.

  12. Leung, J.Y.T., Li, C.L. 2008. Scheduling with processing set restrictions: A survey. International Journal of Production Economics, 116, 251–262.

  13. Leung, J.Y.T., Li, C.L. 2016. Scheduling with processing set restrictions: A literature update. International Journal of Production Economics, 175, 1–11.

  14. Leung, J.Y.T., Ng, C.T. 2017. Fast approximation algorithms for uniform machine scheduling with processing set restrictions. European Journal of Operational Research, 260, 507–513.

  15. Li, S. 2017. Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan. European Journal of Operational Research, 260, 12–20.

  16. Li, W., Li, J., Zhang, T. 2009. Approximation schemes for scheduling on parallel machines with GoS levels. Lecture Notes in Operations Research and Its Applications, 10, 53–60.

  17. Li, C.L., Wang, X. 2010. Scheduling parallel machines with inclusive processing set restrictions and job release times. European Journal of Operational Research, 200, 702–710.

  18. Li, C.L., Li, Q. 2015. Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions. Journal of the Operational Research Society, 66, 516–523.

  19. Li, D., Wang, J., Qiang, R., Chiong, R. 2021. A hybrid differential evolution algorithm for parallel machine scheduling of lace dyeing considering colour families, sequence-dependent setup and machine eligibility. International Journal of Production Research, 59, 2722–2738.

  20. Liao, B., Song, Q., Pei, J., Yang, S., Pardalos, P.M. 2020. Parallel-machine group scheduling with inclusive processing set restrictions, outsourcing option and serial-batching under the effect of step-deterioration. Journal of Global Optimization, 78, 717–742.

  21. Lim, K. 2010. Parallel machines scheduling with GoS eligibility constraints: A survey. Journal of the Korean Institute of Industrial Engineers, 36, 248–254.

  22. Liu, M., Yang, X., Chu, F., Zhang, J., Chu, C. 2020. Energy-oriented bi-objective optimization for the tempered glass scheduling. Omega, 90, 101995.

  23. Maecker, S., Shen, L., Mönch, L. 2023. Unrelated parallel machine scheduling with eligibility constraints and delivery times to minimize total weighted tardiness. Computers & Operations Research, 149, 105999.

  24. Mateo, M., Teghem, J., Tuyttens, D. 2018. A bi-objective parallel machine problem with eligibility, release dates and delivery times of the jobs. International Journal of Production Research, 56, 1030–1053.

  25. Mecler, D., Abu-Marrul, V., Martinelli, R., Hoff, A. 2022. Iterated greedy algorithms for a complex parallel machine scheduling problem. European Journal of Operational Research, 300, 545–560.

  26. Mokotoff, E. 2001. Parallel machine scheduling problems: A survey. Asia-Pacific Journal of Operational Research, 18, 193–242.

  27. Ou, J., Leung, J.Y.T., Li, C.L. 2008. Scheduling parallel machines with inclusive processing set restrictions. Naval Research Logistics, 55, 328–338.

  28. Ou, J., Zhong, X., Qi, X. 2016. Scheduling parallel machines with inclusive processing set restrictions and job rejection. Naval Research Logistics, 63, 667–681.

  29. Pinedo, M. 2002. Scheduling: Theory, algorithm, and system. Second Ed. Prentice-Hall Press. New Jersey. U.S.A.

  30. Planinić, L., Backović, H., Đurasević, M., Jakobović, D. 2022. A comparative study of dispatching rule representations in evolutionary algorithms for the dynamic unrelated machines environment. IEEE Access, 10, 22886–22901.

  31. ReVelle, C., Scholssberg, M., Williams, J. 2008. Solving the maximal covering location problem with heuristic concentration. Computers & Operations Research, 35, 427–435.

  32. Tseng, C.T., Lee, C.H., Chiu, Y.S.P., Lu, W.T. 2017. A discrete electromagnetism-like mechanism for parallel machine scheduling under a grade of service provision. International Journal of Production Research, 55, 3149–3163.

  33. Woeginger, G.J. 2009. A comment on parallel-machine scheduling under a grade of service provision to minimize makespan. Information Processing Letters, 109, 341–342.

  34. Xie, Y., Sheng, Y., Qiu, M., Gui, F. 2022. An adaptive decoding biased random key genetic algorithm for cloud workflow scheduling. Engineering Applications of Artificial Intelligence, 112, 104879.

  35. Zhao, G., Liu, J., Tang, L., Zhao, R., Dong, Y. 2019. Model and heuristic solutions for the multiple double-load crane scheduling problem in slab yards. IEEE Transactions on Automation Science and Engineering, 17, 1307–1319.


ARTICLE INFORMATION

Received: 2023-04-23
Revised: 2023-05-28
Accepted: 2023-06-11
Available Online: 2023-07-18


Cite this article:

Tseng, C.-T., Zhang, S.-F. 2023. Heuristics for parallel machine scheduling with GoS eligibility constraints. International Journal of Applied Science and Engineering, 20, 2023097. https://doi.org/10.6703/IJASE.202309_20(3).009

  Copyright The Author(s). This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY 4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are cited.

Other people also read ...

doaj logo

 

2.3
2022CiteScore
 
 
48th percentile
Powered by  Scopus
 
 

SCImago Journal & Country Rank

IJASE - Most Read Articles

IJASE - Most popular articles