Resource Allocation to Minimize the Makespan with Multi-Resource Operations

WENG Wuyan, CHU Chengbin, WU Peng

Journal of Systems Science & Complexity ›› 2024, Vol. 37 ›› Issue (5) : 2054-2070.

PDF(234 KB)
中国科学院数学与系统科学研究院期刊网
JSSC
PDF(234 KB)
Journal of Systems Science & Complexity ›› 2024, Vol. 37 ›› Issue (5) : 2054-2070. DOI: 10.1007/s11424-024-3284-z

Resource Allocation to Minimize the Makespan with Multi-Resource Operations

  • WENG Wuyan1, CHU Chengbin2, WU Peng1
Author information +
History +

Abstract

This paper investigates a new resource-allocation problem involving multi-resource operations, where completing an operation requires simultaneous use of multiple (renewable) resources, probably of different types. The goal of the study is to provide a solution method that minimizes the makespan. The authors formulate the problem into a novel mixed-integer linear program (MILP) model. To efficiently solve practical-sized instances, an exact Benders decomposition algorithm is developed. This algorithm divides the original problem into a master problem of allocating resources and a subproblem of calculating the makespan, and both are linked via Benders cuts. The convergence is sped up by improving the mathematical model and embedding the variable neighborhood search algorithm. Compared with CPLEX, a commonly used MILP solver, the computational results demonstrate that the proposed algorithm provides tighter upper and lower bounds in most instances. In particular, compared with CPLEX, the proposed method can on average improve the upper and lower bounds by 4.76% and 4.39%, respectively, in solving practical-sized instances.

Key words

Benders decomposition / multi-resources operations / resource allocation

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
WENG Wuyan , CHU Chengbin , WU Peng. Resource Allocation to Minimize the Makespan with Multi-Resource Operations. Journal of Systems Science & Complexity, 2024, 37(5): 2054-2070 https://doi.org/10.1007/s11424-024-3284-z

References

[1] Li S and Zhang Y, On-line scheduling on parallel machines to minimize the makespan, Journal of Systems Science & Complexity, 2016, 29(2): 472-477.
[2] Desprez C, Chu F, and Chu C, Minimising the weighted number of tardy jobs in a hybrid flow shop with genetic algorithm, International Journal of Computer Integrated Manufacturing, 2009, 22(8): 745-757.
[3] Gupta J N D and Ho J C, Minimizing makespan subject to minimum flowtime on two identical parallel machines, Computers & Operations Research, 2001, 28(7): 705-717.
[4] Liao C J, Shyur D L, and Lin C H, Makespan minimization for two parallel machines with an availability constraint, European Journal of Operational Research, 2005, 160(2): 445-456.
[5] He J, Li Q, and Xu D, Scheduling two parallel machines with machine-dependent availabilities, Computers & Operations Research, 2016, 72(1): 31-42.
[6] Wang S, Wu R, Chu F, et al., Identical parallel machine scheduling with assurance of maximum waiting time for an emergency job, Computers & Operations Research, 2020, 118: 104918.
[7] Cai S and Liu K, Heuristics for online scheduling on identical parallel machines with two GoS levels, Journal of Systems Science & Complexity, 2019, 32(4): 1180-1193.
[8] Lu X and Liu Z, An optimal online algorithm for fractional scheduling on uniform machines with three hierarchies, Journal of Systems Science & Complexity, 2016, 29(6): 1650-1657.
[9] Li K, Chen J, Fu H, et al., Uniform parallel machine scheduling with fuzzy processing times under resource consumption constraint, Applied Soft Computing, 2019, 82(1): 1-16.
[10] Wang S, Wu R, Chu F, et al., Unrelated parallel machine scheduling problem with special controllable processing times and setups, Computers & Operations Research, 2022, 148: 105990.
[11] Yilmaz Eroglu D, Ozmutlu H C, and Ozmutlu S, Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent set-up times, International Journal of Production Research, 2014, 52(19): 5841-5856.
[12] Sels V, Coelho J, Dias A M, et al., Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem, Computers & Operations Research, 2015, 53: 107-117.
[13] Maecker S, Shen L, and Monch L, Unrelated parallel machine scheduling with eligibility constraints and delivery times to minimize total weighted tardiness, Computers & Operations Research, 2023, 149: 105999.
[14] Pezzella F, Morganti G, and Ciaschetti G, A genetic algorithm for the flexible job-shop scheduling problem, Computers & Operations Research, 2008, 35(10): 3202-3212.
[15] Zhang G, Gao L, and Shi Y, An effective genetic algorithm for the flexible job-shop scheduling problem, Expert Systems with Applications, 2011, 38(4): 3563-3573.
[16] De Giovanni L and Pezzella F, An improved genetic algorithm for the distributed and flexible job-shop scheduling problem, European Journal of Operational Research, 2010, 200(2): 395-408.
[17] Yazdani M, Amiri M, and Zandieh M, Flexible job-shop scheduling with parallel variable neighborhood search algorithm, Expert Systems with Applications, 2010, 37(1): 678-687.
[18] Bagheri A, Zandieh M, Mahdavi I, et al., An artificial immune algorithm for the flexible job-shop scheduling problem, Future Generation Computer Systems, 2010, 26(4): 533-541.
[19] Li M and Lei D, An imperialist competitive algorithm with feedback for energy-efficient flexible job shop scheduling with transportation and sequence-dependent setup times, Engineering Applications of Artificial Intelligence, 2021, 103: 1-13.
[20] Han D, Tang Q, Zhang Z, et al., An improved migrating birds optimization algorithm for a hybrid flow shop scheduling within steel plants, Mathematics, 2020, 8(10): 1-28.
[21] Marichelvam M K, Prabaharan T, and Yang X S, Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan, Applied Soft Computing, 2014, 19: 93-101.
[22] Shao W, Shao Z, and Pi D, Modeling and multi-neighborhood iterated greedy algorithm for distributed hybrid flow shop scheduling problem, Knowledge-Based Systems, 2020, 194: 1-17.
[23] Lin J T and Chen C M, Simulation optimization approach for hybrid flow shop scheduling problem in semiconductor back-end manufacturing, Simulation Modelling Practice and Theory, 2015, 51: 100-114.
[24] Botta-Genoulaz V, Hybrid flow shop scheduling with precedence constraints and time lags to minimize maximum lateness, International Journal of Production Economics, 2000, 64(1-3): 101-111.
[25] Dugardin F, Yalaoui F, and Amodeo L, New multi-objective method to solve reentrant hybrid flow shop scheduling problem, European Journal of Operational Research, 2010, 203(1): 22-31.
[26] Manaa A and Chu C, Scheduling multiprocessor tasks to minimise the makespan on two dedicated processors, European Journal of Industrial Engineering, 2010, 4(3): 265-279.
[27] Dauzère-Pérès S, Roux W, and Lasserre J B, Multi-resource shop scheduling with resource flexibility, European Journal of Operational Research, 1998, 107(2): 289-305.
[28] Mati Y and Xie X, Multiresource shop scheduling with resource flexibility and blocking, IEEE Transactions on Automation Science and Engineering, 2010, 8(1): 175-189.
[29] Huh W T, Liu N, and Truong V A, Multiresource allocation scheduling in dynamic environments, Manufacturing & Service Operations Management, 2013, 15(2): 280-291.
[30] Artigues C, Michelon P, and Reusser S, Insertion techniques for static and dynamic resourceconstrained project scheduling, European Journal of Operational Research, 2003, 149(2): 249- 267.
[31] Gao L and Pan Q K, A shuffled multi-swarm micro-migrating birds optimizer for a multi-resourceconstrained flexible job shop scheduling problem, Information Sciences, 2016, 372: 655-676.
[32] BnnoBRs J, Partitioning procedures for solving mixed-variables programming problems, Numer. Math, 1962, 4(1): 238-252.
[33] Hamzaday A, An effective benders decomposition algorithm for solving the distributed permutation flowshop scheduling problem, Computers & Operations Research, 2020, 123: 1-15.
[34] Wu X and Che A, Energy-efficient no-wait permutation flow shop scheduling by adaptive multiobjective variable neighborhood search, Omega, 2020, 94: 1-16.
[35] Liu L, Outsourcing and rescheduling for a two-machine flow shop with the disruption of new arriving jobs: A hybrid variable neighborhood search algorithm, Computers & Industrial Engineering, 2019, 130: 198-221.

Funding

This research was supported by the National Natural Science Foundation of China under Grant Nos. 71871159, 71701049, and 71901069, National Social Science Foundation of China under Grant No. 22BGL272, Humanities and Social Science Foundation of the Chinese Ministry of Education under Grant No. 21YJA630096, Natural Science Foundation of Fujian Province, China under Grant Nos. 2020J05040 and 2022J01075.
PDF(234 KB)

78

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉