×

Single workgroup scheduling problem with variable processing personnel. (English) Zbl 07191574

Summary: Human resources have played an important role in the production systems of manufacturing enterprises. At the same time, human resource allocation, as a scheduling problem, has attracted more and more attention from the industry and academia, with the increasing complexity of technology and the rising cost of workforce. However, the existing scheduling methods fail to fully consider the relationship between tasks and employees. In this paper we consider a single workgroup scheduling problem with the assumption of human resources variability. Jobs must be assigned to employees, where the number of processing personnel and the processing time are variable for one job. We model the problem as a combinatorial optimization problem and the objective considered is to minimize the maximum finish time which is called makespan. This problem is transformed into a two-dimension rectangle strip packing problem and we propose a hybrid optimization algorithm which combines scheduling algorithm with packing algorithm. Finally, different size cases are adopted to test the model. Results show the proposed strategy and algorithm are suitable for solving single workgroup scheduling very well.

MSC:

90Bxx Operations research and management science
Full Text: DOI

References:

[1] Alves, C.; de Carvalho, JV; Clautiaux, F.; Rietz, J., Multi dimensional dual-feasible functions and fast lower bounds for the vector packing problem, Eur J Oper Res, 233, 43-63 (2014) · Zbl 1339.90235 · doi:10.1016/j.ejor.2013.08.011
[2] Billaut, J-C; Della Croce, F.; Grosso, A., A single machine scheduling problem with two-dimensional vector packing constraints, Eur J Oper Res, 243, 1, 75-81 (2015) · Zbl 1346.90327 · doi:10.1016/j.ejor.2014.11.036
[3] Burke, EK; Kendall, G.; Whitwell, G., A new placement heuristic for the orthogonal stock-cutting problem, Oper Res, 52, 4, 655-671 (2004) · Zbl 1165.90690 · doi:10.1287/opre.1040.0109
[4] Dahmani, N.; Clautiaux, François; Krichen, S.; Talbi, EG, Iterative approaches for solving a multi-objective 2-dimensional vector packing problem, Comput Ind Eng, 66, 1, 158-170 (2013) · doi:10.1016/j.cie.2013.05.016
[5] De Carvalho, JMV, Lp models for bin packing and cutting stock problems, Eur J Oper Res, 141, 2, 253-273 (2002) · Zbl 1059.90095 · doi:10.1016/S0377-2217(02)00124-8
[6] Dósa, György; Fügenschuh, Armin; Tan, Z., Tight upper bounds for semi-online scheduling on two uniform machines with known optimum, Cent Eur J Oper Res, 26, 1, 161-180 (2018) · Zbl 1390.90310 · doi:10.1007/s10100-017-0481-z
[7] Fanjul-Peyro, L.; Perea, F.; Ruiz, Rubén, Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources, Eur J Oper Res, 260, 2, 482-493 (2017) · Zbl 1403.90320 · doi:10.1016/j.ejor.2017.01.002
[8] Hifi, M., Exact algorithms for the guillotine strip cutting/packing problem, Comput Oper Res, 25, 11, 925-940 (1998) · Zbl 1040.90568 · doi:10.1016/S0305-0548(98)00008-2
[9] Horváth, Markó; Kis, Tamás, Computing strong lower and upper bounds for the integrated multiple- depot vehicle and crew scheduling problem with branch-and-price, Cent Eur J Oper Res, 27, 1, 39-67 (2019) · Zbl 07024039 · doi:10.1007/s10100-017-0489-4
[10] Hu, Q.; Lim, A.; Zhu, W., The two-dimensional vector packing problem with piecewise linear cost function, Omega, 50, 43-53 (2015) · doi:10.1016/j.omega.2014.07.004
[11] Kartak, VM; Ripatti, AV, The minimum raster set problem and its application to the d -dimensional orthogonal packing problem, Eur J Oper Res, 271, 1, 33-39 (2018) · Zbl 1403.90574 · doi:10.1016/j.ejor.2018.04.046
[12] Kim, HJ, Bounds for parallel machine scheduling with predefined parts of jobs and setup time, Ann Oper Res, 261, 1-2, 401-412 (2018) · Zbl 1384.90045 · doi:10.1007/s10479-017-2615-z
[13] Lawler, EL, A “Pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness, Ann Discret Math, 1, 331-342 (1977) · Zbl 0353.68071 · doi:10.1016/S0167-5060(08)70742-8
[14] Lesh, N.; Marks, J.; McMahon, A.; Mitzenmacher, M., Exhaustive approaches to 2D rectanglar perfect packings, Inform Process Lett, 90, 7-14 (2004) · Zbl 1170.90523 · doi:10.1016/j.ipl.2004.01.006
[15] Manne, AS, On the job-shop scheduling problem, Oper Res, 8, 219-223 (1960) · doi:10.1287/opre.8.2.219
[16] Marinelli, F.; Pizzuti, A., A sequential value correction heuristic for a bi-objective two-dimensional bin-packing, Electron Notes Discret Math, 64, 25-34 (2018) · Zbl 1392.90014 · doi:10.1016/j.endm.2018.01.004
[17] Martello, S.; Monaci, M.; Vigo, D., An exact approach to the strip-packing problem, Informs J Comput, 15, 3, 310-319 (2003) · Zbl 1238.90116 · doi:10.1287/ijoc.15.3.310.16082
[18] Peng, BT; Zhou, YW, Recursive heuristic algorithm for the 2D rectangular strip packing problem, J Softw, 23, 10, 2600-2611 (2012) · Zbl 1274.68435 · doi:10.3724/SP.J.1001.2012.04187
[19] Polyakovskiy, S.; M’Hallah, Rym, A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due dates, Eur J Oper Res, 266, 3, 818-839 (2018) · Zbl 1403.90486 · doi:10.1016/j.ejor.2017.10.046
[20] Rajkanth, R.; Rajendran, C.; Ziegler, H., Heuristics to minimize the completion time variance of jobs on a single machine and on identical parallel machines, Int J Adv Manuf Technol, 88, 5-8, 1923-1936 (2017) · doi:10.1007/s00170-016-8879-7
[21] Tapia, JFD; Lee, J-Y; Ooi, REH; Foo, DCY; Tan, RR, Planning and scheduling of CO 2 capture, utilization and storage (CCUS) operations as a strip packing problem, Process Saf Environ, 104, 358-372 (2016) · doi:10.1016/j.psep.2016.09.013
[22] Van Hulle, MM, A goal programming network for mixed integer linear programming: a case study for the job-shop scheduling problem, Int J Neural Syst, 2, 3, 201-209 (1991) · doi:10.1142/S0129065791000182
[23] Walter, R., A note on minimizing the sum of squares of machine completion times on two identical parallel machines, Cent Eur J Oper Res, 25, 1, 139-144 (2017) · Zbl 1364.90165 · doi:10.1007/s10100-015-0429-0
[24] Zhang, D.; Shi, L.; Leung, SCH; Wu, T., A priority heuristic for the guillotine rectangular packing problem, Inform Process Lett, 116, 1, 15-21 (2016) · doi:10.1016/j.ipl.2015.08.008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.