Identical Parallel Machine Scheduling Considering Workload Smoothness Index
Source abstract
Abstract
Workload balance is significant in the manufacturing industry. However, on the one hand, some existing specific criteria cannot achieve the minimization workload imbalance of parallel machines. On the other hand, there are few algorithms in existing studies that can effectively solve the parallel machine scheduling problem with the objective of minimizing workload imbalance. Inspired by this, we investigate an identical parallel machine scheduling problem with the objective of the minimum workload smoothness index. We first establish a mathematical model for the considered problem and then linearize its objective function. We prove the NP-hardness of the problem by reducing the PARTITION problem to it, and we provide both the upper bound and lower bound of the studied problem. An efficient genetic algorithm and an improved list scheduling algorithm are also proposed to efficiently address the considered problem. The numerical results demonstrate the effectiveness of the proposed methods.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Scheduling and Optimization Algorithms · Assembly Line Balancing Optimization · Advanced Manufacturing and Logistics Optimization
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, China
School of Economics and Management, Tongji University, Shanghai 200092, China
Funding
National Natural Science Foundation of China · Fundamental Research Funds for the Central Universities
References (32)
Show source-provided references
1. Parallel machine scheduling with stochastic release times and processing times10.1080/00207543.2020.1812752 ↗
2. Parallel machine scheduling with multiple processing alternatives and sequence-dependent setup times10.1080/00207543.2020.1781278 ↗
3. Parallel machine scheduling problems: A survey
4. Exact algorithms to minimize makespan on single and parallel batch processing machines10.1016/j.ejor.2020.01.065 ↗
5. A branch-and-bound algorithm for the two-machine total completion time flowshop problem subject to release dates
6. Approximation algorithms for makespan minimization on identical parallel machines under resource constraints10.1080/01605682.2020.1772019 ↗
7. Two-agent scheduling on unrelated parallel machines with total completion time and weighted number of tardy jobs criteria10.1007/s10951-018-0583-z ↗
8. An iterated min-max procedure for practical workload balancing on non-Identical parallel machines in manufacturing systems10.1016/j.ejor.2019.06.007 ↗
9. Ouazene, Y., Nguyen, N.Q., and Yalaoui, F. (2021). Workload balancing on identical parallel machines: Theoretical and computational analysis. Appl. Sci., 11.10.3390/app11083677 ↗
10. Xu, G.Y., Guan, Z.L., Yue, L., Mumtaz, J., and Liang, J. (2021). Modeling and optimization for multi-objective nonidentical parallel machining line scheduling with a jumping process operation constraint. Symmetry, 13.10.3390/sym13081521 ↗
11. Workflow balancing strategies in parallel machine scheduling10.1007/s00170-003-1603-4 ↗
12. An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times10.1016/j.cor.2010.12.003 ↗
13. An operator load-balancing problem in a semi-automatic parallel machine shop10.1016/j.cie.2003.12.015 ↗
14. Unrelated parallel machine selection and job scheduling with the objective of minimizing total workload and machine fixed costs10.1109/TASE.2018.2832440 ↗
15. A heuristic method of assembly line balancing for assumptions of constant or variable work element times
16. Workload balancing in identical parallel machine scheduling using a mathematical programming method10.1080/18756891.2013.853932 ↗
17. Parallel machine scheduling with load balancing and sequence dependent setups
18. Minimizing the normalized sum of square for workload deviations on m parallel processors10.1016/j.cie.2008.05.003 ↗
19. A note on minimizing the normalized sum of squared workload deviations on m parallel processors10.1016/j.cie.2014.07.004 ↗
20. A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines10.1016/j.cor.2016.03.008 ↗
21. Single CNC machine scheduling with controllable processing times to minimize total weighted tardiness10.1016/j.cor.2010.09.004 ↗
22. Stochastic optimization of two-machine flow shop robotic cells with controllable inspection times: From theory toward practice10.1016/j.rcim.2019.101822 ↗
23. A heuristic-based genetic algorithm for workload smoothing in assembly lines10.1016/S0305-0548(97)00046-4 ↗
24. Balancing and sequencing of assembly lines contributions to management science
25. Balancing mixed-model assembly lines: A computational evaluation of objectives to smoothen workload10.1080/00207540902810577 ↗
26. Maximizing production rate and workload smoothing in assembly lines using particle swarm optimization10.1016/j.ijpe.2010.10.016 ↗
27. Workload smoothing in simple assembly line balancing10.1016/j.cor.2017.08.006 ↗
28. Workers’ rest allowance and smoothing of the workload in assembly lines10.1080/00207543.2019.1616847 ↗
29. An efficient two-stage genetic algorithm for a flexible job-shop scheduling problem with sequence dependent attached/detached setup, machine release date and lag-time10.1016/j.cie.2020.106605 ↗
30. A genetic column generation algorithm for sustainable spare part delivery: Application to the Sydney DropPoint network10.1007/s10479-018-2911-2 ↗
31. Two yard crane scheduling with dynamic processing time and interference10.1109/TITS.2017.2780256 ↗
32. Workflow balancing in parallel machines through genetic algorithm10.1007/s00170-006-0553-z ↗