Study on resource allocation scheduling problem with learning factors and group technology

Jia-Xuan Yan; Na Ren; Hong-Bin Bei; Han Bao; Ji-Bo Wang

doi:10.3934/jimo.2022091

Article Contents

2023, Volume 19, Issue 5: 3419-3435. Doi: 10.3934/jimo.2022091

This issue Previous Article A bi-objective integrated mathematical model for blood supply chain: Case of Turkish red crescent Next Article Application of sphere packing theory in financial management

Study on resource allocation scheduling problem with learning factors and group technology

School of Science, Shenyang Aerospace University, Shenyang 110136, China

*Corresponding author
*Corresponding author

Received: March 2022

Revised: April 2022

Early access: June 2022

Published: May 2023

This Work Was Supported by LiaoNing Revitalization Talents Program (grant no. XLYC2002017) and the Natural Science Foundation of LiaoNing Province in China (grant no. 2020-MS-233)

Abstract Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by

Abstract

This paper investigates the single-machine resource allocation scheduling problem with learning effects and group technology. The objective is to determine the optimal job and group schedules, and resource allocations such that total completion time is minimized subject to limited resource availability. For some special cases, we show that the problem remains polynomially solvable. For general case of the problem, we propose the heuristic algorithm, tabu search algorithm and branch-and-bound algorithm. Numerical experiments are tested to evaluate the performance of the heuristic and branch-and-bound algorithms.

Keywords:

Mathematics Subject Classification: Primary: 90B35; Secondary: 90C26.

Citation:

Full Text(HTML)

Table 1. Symbols used in this paper

Symbol	Meaning
$ \bar{n} $	number of jobs
$ \bar{m} $	number of groups $ \left(\bar{m}\ge2\right) $
$ \bar{G} _{i} $	group $ i $, $ i=1,2,\dots ,\bar{m} $
$ \bar{n} _{i} $	number of jobs belonging to group $ \bar{G} _{i} $,
	i.e., $ \bar{n} _{1}+\bar{n} _{2}+\cdots +\bar{n} _{\bar{m}}=\bar{n} $
$ \bar{J} _{ij} $	job $ j $ at group $ \bar{G} _{i} $
$ \alpha _{ij} $	normal processing time of job $ \bar{J} _{ij} $,
	i.e., the processing time without any learning effects
	and resource allocation
$ \bar{u} _{ij} $	amount of non-renewable resources assigned to job $ \bar{J} _{ij} $
$ p_{ij}^{A} $	actual processing time of job $ \bar{J} _{ij} $
$ \beta _{i} $	normal setup time of group $ \bar{G} _{i} $, $ i=1\dots ,\bar{m} $,
	i.e., setup time without any learning effects and resource allocation
$ \bar{u}_{i} $	amount of non-renewable resources allocated to group $ \bar{G} _{i} $
$ s_{i}^{A} $	actual setup time of group $ \bar{G} _{i} $
$ \bar{C} _{ij} $	completion time of job $ \bar{J} _{ij} $
$ [j] $	$ j $th position in a sequence
$ {\sum_{i=1}^{\bar{m}}\sum_{j=1}^{\bar{n} _{i} }\bar{C} _{ij } } $	total completion time of all jobs
$ \bar{\pi} _{G} $	schedule of groups
$ \bar{\pi} _{i} $	schedule of jobs in group $ \bar{G} _{i} $
$ \bar{\pi} $	order of all jobs, i.e., $ \bar{\pi}=\left (\bar{\pi} _{G},\bar{\pi} _{1} ,\bar{\pi} _{2},\dots ,\bar{\pi} _{m} \right ) $

| Show Table

DownLoad: CSV

Table 2. Results of Algorithms for a_i ~ (−0.5, 0), i = 1, 2, 3

		B & B-CPU time (s)		Node number of B & B		HA-CPU time (s)		error percentage of HA (%)		TS-CPU time (s)		error percentage of TS (%)
$\bar{n}$	$\bar{m}$	mean	max	mean	max	mean	max	mean	max	mean	max	mean	max
	12	92.60375	118.45	40201	64473	0.012	0.014	0.3086155	3.2049018	34.5413	54.9445	1.8784662	7.0004741
	14	147.8928	407.195	894252	1409007	0.015	0.017	0.3725094	3.0971855	44.9875	55.9261	2.6714223	4.3642932
100	16	398.2345	996.181	2409852	6999847	0.019	0.202	0.4233452	4.0211423	41.3313	63.4353	3.0923353	6.3526434
	18	1034.523	2771.96	5623532	9714771	0.022	0.305	0.2231322	2.3132432	45.0924	65.0242	2.9502345	3.4252623
	20	1693.521	3005.421	8729523	15850787	0.019	0.551	0.4920423	1.9843322	51.3256	119.0963	2.3143245	6.9902345
	12	101.235	128.868	60932	397115	0.011	0.021	0.0394613	1.1267179	40.3735	90.5195	2.1547218	5.2201993
	14	144.923	660.523	782354	991123	0.023	0.532	0.2266826	1.0658756	52.7042	98.1406	2.1960548	4.3782459
150	16	667.523	1937.1	2209423	8713113	0.012	0.914	0.1375955	2.1714648	55.3457	150.5454	3.0800341	6.2318945
	18	1109.524	2799.095	8769423	20093423	0.104	0.546	0.1598375	1.2963865	59.7642	175.1385	2.1322938	6.4416128
	20	1779.425	3600	19042352	25586760	0.201	0.747	0.0656878	2.0542139	60.3437	200.6248	3.0418666	6.7267963
	12	119.523	304.522	54364	449452	0.034	0.04	0.1411345	2.0722864	43.6439	90.0991	1.0515623	4.4235238
200	14	820.342	974.234	831243	1102345	0.128	0.857	0.2036596	3.1779763	55.7958	95.5008	1.0713272	5.3979361
	16	1046.1216	1600.9841	5840773	7514382	0.234	1.148	0.2037897	1.1998882	58.2666	159.3643	2.0796723	4.0275603
	18	2783.235	3533.423	9105668	15394402	0.259	1.103	0.2804085	1.0943255	60.1218	184.7286	2.0527157	5.2066514
	20	3304.523	3600	24085333	26357637	0.238	1.136	0.394613	1.20511586	60.3825	211.1966	3.1935832	6.2386858
	12	182.423	305.423	60932	579342	0.227	0.446	0.2266825	3.0647742	46.0333	100.5567	1.0991656	4.1353416
	14	899.423	998.523	892345	1112343	0.145	0.985	0.3759356	1.2600473	50.1835	114.6852	1.0658337	5.2622463
250	16	1449.522	1996.421	8998876	10006535	0.717	1.162	0.5983676	1.2119063	59.7307	133.7937	2.0668333	5.4633234
	18	1759.7241	3600	14430645	26559574	0.638	1.029	0.6568783	2.1963868	60.1297	197.2888	3.0678536	6.0852372
	20	3505.234	3600	22007867	26359611	0.948	1.649	0.4113435	1.0604905	60.9629	213.3254	2.0158012	6.0816978
	12	208.523	333.522	89043	730523	0.249	0.537	0.5036593	3.2633721	50.5559	100.6547	1.1708226	5.0941733
	14	833.623	1010.423	854319	1236453	0.245	0.917	0.5037896	2.2693285	50.5686	109.3466	1.1985641	6.2706675
300	16	1192.425	2130.032	9987567	14457445	0.524	1.181	0.6804087	3.1476188	60.1988	175.4708	3.0693548	6.0989441
	18	2503.524	3600	10003234	26884563	1.112	1.198	0.6150571	3.0156195	63.3092	199.4753	3.0222123	9.4235233
	20	3566.524	3600	25670423	26004523	1.523	1.986	0.7558253	3.0175937	65.7919	220.5352	4.1256354	7.2535165

| Show Table

DownLoad: CSV

Table 3. Results of Algorithms for a_i ~ (−1, −0.5), i = 1, 2, 3

		B & B-CPU time (s)		Node number of B & B		HA-CPU time (s)		error percentage of HA (%)		TS-CPU time (s)		error percentage of TS (%)
$\bar{n}$	$\bar{m}$	mean	max	mean	max	mean	max	mean	max	mean	max	mean	max
	12	91.422	174.255	77254	84562	0.017	0.021	0.5294324	1.6881844	54.103	90.393	1.1692221	2.0584123
	14	155.234	491.234	706353	2272534	0.065	0.345	0.5579595	1.7150142	49.114	174.565	2.1206775	3.1303934
100	16	319.524	678.152	2194621	6973422	0.124	0.952	0.7137092	2.4436245	53.796	153.235	2.2213632	5.3202546
	18	1212.757	2313.413	5357833	14527582	0.334	1.994	0.4253476	1.7162733	55.366	190.505	3.4406966	5.1076952
	20	1833.432	2999.521	8073570	18059612	0.894	2.423	0.7197775	2.7930113	60.524	201.428	3.3731662	5.4362341
	12	132.445	233.422	178342	539823	0.038	0.045	0.1163187	1.1433093	50.798	100.531	1.6072212	3.6451534
	14	351.764	1103.112	2315262	4992345	0.116	0.452	0.4751776	1.5941911	49.609	115.381	1.7700991	4.6826412
150	16	792.522	2200.421	4269431	8935663	0.362	1.943	0.6241856	1.1693295	67.144	130.764	2.6618615	4.3549482
	18	1812.666	3198.423	9215245	27894235	0.743	2.229	0.8003645	3.3124777	57.479	153.769	3.7020813	5.0186688
	20	3569.514	3600	29924256	31042352	0.942	2.991	0.9601373	2.6087314	60.209	175.685	3.6708784	7.1662056
	12	110.627	219.534	89932	552345	0.058	0.066	0.6219684	2.5455855	50.324	108.604	2.2471187	3.6263636
200	14	612.423	779.144	2485215	6992354	0.099	1.032	0.7219854	2.7689695	58.576	170.629	2.5098163	4.0250416
	16	1799.634	2187.433	10005345	12024235	0.342	1.116	0.6948743	3.0696235	58.001	163.124	4.4846142	6.0746901
	18	2001.523	3600	15534255	19001453	0.431	1.532	0.7707673	3.5620543	59.495	212.372	3.1043425	10.5240043
	20	2623.663	3600	19884254	19942786	0.857	1.852	0.7793331	3.0444759	60.131	253.129	5.0687413	9.5276885
	12	128.521	241.523	100432	562451	0.135	0.253	0.2088543	1.3058191	52.569	123.432	2.1357112	4.0584125
	14	589.623	617.042	4425236	6326431	0.267	0.555	0.3134454	1.7072163	61.465	177.812	2.1010853	5.1303932
250	16	1791.965	2571.445	10106341	13256342	0.657	1.193	0.7759925	1.5774863	65.096	262.223	3.5341266	5.3202543
	18	3342.522	3600	21996259	21534614	0.932	1.245	0.5032063	2.2094454	59.546	268.558	4.2611798	8.1076956
	20	3458.531	3600	24560631	25623134	1.089	1.898	0.9760725	2.1465018	70.573	269.179	4.3458089	8.4362564
	12	185.522	298.543	193141	824521	0.234	0.432	0.4501721	0.6345429	50.744	153.568	2.4000243	5.6451536
	14	601.663	756.322	852089	6899466	0.557	0.785	0.4449465	0.7460143	56.187	201.188	2.0115512	5.6826414
300	16	2220.643	2799.533	8794252	13478865	0.574	1.299	0.6219685	1.6562852	60.229	275.361	3.5408975	6.3549484
	18	3001.643	3600	18735223	19826416	0.964	1.193	0.6198514	2.5821484	64.621	331.738	4.4569893	7.0186688
	20	3495.613	3600	24863451	25742565	1.098	2.984	0.9487584	3.1587155	68.474	335.413	4.6089174	7.4561565

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Azzouz, M. Ennigrou and L. B. Said, Scheduling problems under learning effects: Classification and cartography,, International Journal of Production Research, 56 (2018), 1642-1661.
[2]	G.-H. Hardy, J.-E. Littlewood and G. Polya, Inequalities, 2$^nd$ edition Cambridge, UK: Cambridge University Press, 1967.
[3]	X. Huang, Bicriterion scheduling with group technology and deterioration effect, Journal of Applied Mathematics and Computing, 60 (2019), 455-464. doi: 10.1007/s12190-018-01222-1.
[4]	X. Huang, M.-Z. Wang and J.-B. Wang, Single-machine group scheduling with both learning effects and deteriorating jobs, Computers & Industrial Engineering, 60 (2011), 752-754. doi: 10.1016/j.apm.2009.12.017.
[5]	X.-X. Liang, M. Liu, Y.-B. Feng, J.-B. Wang and L.-S. Wen, Solution algorithms for single-machine resource allocation scheduling with deteriorating jobs and group technology, Engineering Optimization, 52 (2020), 1184-1197. doi: 10.1080/0305215X.2019.1638920.
[6]	W. Liu, X. Hu and X.-Y. Wang, Single machine scheduling with slack due dates assignment, Engineering Optimization, 49 (2017), 709-717. doi: 10.1080/0305215X.2016.1197611.
[7]	L. Liu, J.-J. Wang and X.-Y. Wang, Single machine due-window assignment scheduling with resource-dependent processing times to minimise total resource consumption cost, International Journal of Production Research, 54 (2016), 1186-1195.
[8]	F. Liu, B. Niu, M. Xing, L. Wu and Y. Feng, Optimal cross-trained worker assignment for a hybrid seru production system to minimize makespan and workload imbalance, Computers & Industrial Engineering, 160 (2021), 107552.
[9]	F. Liu, J. Yang and Y.-Y. Lu, Solution algorithms for single-machine group scheduling with ready times and deteriorating jobs, Engineering Optimization, 51 (2019), 862-874. doi: 10.1080/0305215X.2018.1500562.
[10]	Y.-Y. Lu and J.-Y. Liu, A note on resource allocation scheduling with position-dependent workloads, Engineering Optimization, 50 (2018), 1810-1827. doi: 10.1080/0305215X.2017.1414207.
[11]	Y. -Y. Lu, F. Teng and Z. -X. Feng, Scheduling jobs with truncated exponential sum-of-logarithm-processing-times based and position-based learning effects, Asia-Pacific Journal of Operational Research, 32 (2015), 1550026, 17 pp. doi: 10.1142/S0217595915500268.
[12]	Y.-Y. Lu, J.-B. Wang, P. Ji and H. He, A note on resource allocation scheduling with group technology and learning effects on a single machine, Engineering Optimization, 49 (2017), 1621-1632. doi: 10.1080/0305215X.2016.1265305.
[13]	D.-Y. Lv, S.-W. Luo, J. Xue, J.-X. Xu and J.-B. Wang, A note on single machine common flow allowance group scheduling with learning effect and resource allocation, Computers & Industrial Engineering, 151 (2021), 106941.
[14]	D.-Y. Lv and J.-B. Wang, Study on resource-dependent no-wait flow shop scheduling with different due-window assignment and learning effects, Asia-Pacific Journal of Operational Research, 38 (2021), 2150008. doi: 10.1142/s0217595921500081.
[15]	D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 155 (2007), 1643-1666. doi: 10.1016/j.dam.2007.02.003.
[16]	X. Sun, X. Geng and F. Liu, Flow shop scheduling with general position weighted learning effects to minimise total weighted completion time, Journal of the Operational Research Society, 72 (2021), 2674-2689.
[17]	J.-B. Wang, M. Gao, J.-J. Wang, L. Liu and H. He, Scheduling with a position-weighted learning effect and job release dates, Engineering Optimization, 52 (2020), 1475-1493. doi: 10.1080/0305215X.2019.1664498.
[18]	J.-B. Wang, X. Huang and Y.-B. Wu, Group scheduling with independent setup times, ready times, and deteriorating job processing times, The international journal of advanced manufacturing technology, 60 (2012), 643-649.
[19]	D. Wang, Y. Huo and P. Ji, Single-machine group scheduling with deteriorating jobs and allotted resource, Optimization Letters, 8 (2014), 591-605. doi: 10.1007/s11590-012-0577-2.
[20]	J.-B. Wang and X.-X. Liang, Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint, Engineering Optimization, 51 (2019), 231-246. doi: 10.1080/0305215X.2018.1454442.
[21]	X. Wang, W. Liu, L. Li, P. Zhao and R. Zhang, Single-machine scheduling with due date assignment, positional-dependent weights and proportional setup times, Mathematical Biosciences and Engineering, 19 (2022a), 5104-5119. doi: 10.3934/mbe.2022238.
[22]	J.-B. Wang, F. Liu and J.-J. Wang, Research on $m$-machine flow shop scheduling with truncated learning effects, International Transactions in Operational Research, 26 (2019), 1135-1151. doi: 10.1111/itor.12323.
[23]	J.-B. Wang, L. Liu, J.-J. Wang and L. Li, Makespan minimization scheduling with ready times, group technology and shortening job processing times, The Computer Journal, 61 (2018), 1422-1428. doi: 10.1093/comjnl/bxy007.
[24]	J.-B. Wang, M. Liu, N. Yin and P. Ji, Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects, Journal of Industrial and Management Optimization, 13 (2017), 1025-1039. doi: 10.3934/jimo.2016060.
[25]	J.-B. Wang, D.-Y. Lv, J. Xu, P. Ji and F. Li, Bicriterion scheduling with truncated learning effects and convex controllable processing times, International Transactions in Operational Research, 28 (2021), 1573-1593. doi: 10.1111/itor.12888.
[26]	J.-B. Wang and M.-Z. Wang, Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times, Asia-Pacific Journal of Operational Research, 31 (2014), 1450036. doi: 10.1142/S0217595914500365.
[27]	J.-B. Wang and J.-J. Wang, Research on scheduling with job-dependent learning effect and convex resource dependent processing times, International Journal of Production Research, 53 (2015), 5826-5836. doi: 10.1142/S0217595915500335.
[28]	J.-B. Wang, M.-Z. Wang and P. Ji, Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs, International Journal of Systems Science, 43 (2012), 861-868. doi: 10.1080/00207721.2010.542837.
[29]	J.-B. Wang, B. Zhang and H. He, A unified analysis for scheduling problems with variable processing times, Journal of Industrial and Management Optimization, 18 (2022b), 1063-1077. doi: 10.3934/jimo.2021008.
[30]	C.-C. Wu, W.-C. Lee and M.-J. Liou, Single-machine scheduling with two competing agents and learning consideration, Information Sciences, 251 (2013), 136-149. doi: 10.1016/j.ins.2013.06.054.
[31]	Y. Yin, T. C. E. Cheng, C.-C. Wu and S.-R. Cheng, Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time, Journal of the Operational Research Society, 65 (2014), 1-13.
[32]	S. Zhao, Resource allocation flowshop scheduling with learning effect and slack due window assignment, Journal of Industrial and Management Optimization, 17 (2021), 2817-2835. doi: 10.3934/jimo.2020096.
[33]	Z.-G. Zhu, L.-Y. Sun, F. Chu and M. Liu, Single-machine group scheduling with resource allocation and learning effect, Computers & Industrial Engineering, 60 (2011), 148-157.