-
Previous Article
Image space analysis for uncertain multiobjective optimization problems: Robust optimality conditions
- JIMO Home
- This Issue
-
Next Article
Valuing equity-linked death benefits with a threshold expense structure under a regime-switching Lévy model
Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.
Readers can access Online First articles via the “Online First” tab for the selected journal.
Study on resource allocation scheduling problem with learning factors and group technology
School of Science, Shenyang Aerospace University, Shenyang 110136, China |
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.
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.
|
show all references
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.
|
Symbol | Meaning |
number of jobs | |
number of groups |
|
group |
|
number of jobs belonging to group |
|
i.e., |
|
job |
|
normal processing time of job |
|
i.e., the processing time without any learning effects | |
and resource allocation | |
amount of non-renewable resources assigned to job |
|
actual processing time of job |
|
normal setup time of group |
|
i.e., setup time without any learning effects and resource allocation | |
amount of non-renewable resources allocated to group |
|
actual setup time of group |
|
completion time of job |
|
total completion time of all jobs | |
schedule of groups | |
schedule of jobs in group |
|
order of all jobs, i.e., |
Symbol | Meaning |
number of jobs | |
number of groups |
|
group |
|
number of jobs belonging to group |
|
i.e., |
|
job |
|
normal processing time of job |
|
i.e., the processing time without any learning effects | |
and resource allocation | |
amount of non-renewable resources assigned to job |
|
actual processing time of job |
|
normal setup time of group |
|
i.e., setup time without any learning effects and resource allocation | |
amount of non-renewable resources allocated to group |
|
actual setup time of group |
|
completion time of job |
|
total completion time of all jobs | |
schedule of groups | |
schedule of jobs in group |
|
order of all jobs, i.e., |
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 (%) | ||||||||
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 |
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 (%) | ||||||||
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 |
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 (%) | ||||||||
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 |
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 (%) | ||||||||
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 |
[1] |
Shuang Zhao. Resource allocation flowshop scheduling with learning effect and slack due window assignment. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2817-2835. doi: 10.3934/jimo.2020096 |
[2] |
Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial and Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499 |
[3] |
Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104 |
[4] |
Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial and Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647 |
[5] |
Ji-Bo Wang, Dan-Yang Lv, Shi-Yun Wang, Chong Jiang. Resource allocation scheduling with deteriorating jobs and position-dependent workloads. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022011 |
[6] |
Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial and Management Optimization, 2022, 18 (1) : 1-24. doi: 10.3934/jimo.2020140 |
[7] |
Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2567-2578. doi: 10.3934/jimo.2021081 |
[8] |
Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007 |
[9] |
Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088 |
[10] |
Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial and Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060 |
[11] |
Qiying Hu, Wuyi Yue. Optimal control for resource allocation in discrete event systems. Journal of Industrial and Management Optimization, 2006, 2 (1) : 63-80. doi: 10.3934/jimo.2006.2.63 |
[12] |
Sedighe Asghariniya, Hamed Zhiani Rezai, Saeid Mehrabian. Resource allocation: A common set of weights model. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 257-273. doi: 10.3934/naco.2020001 |
[13] |
Irina Kareva, Faina Berezovkaya, Georgy Karev. Mixed strategies and natural selection in resource allocation. Mathematical Biosciences & Engineering, 2013, 10 (5&6) : 1561-1586. doi: 10.3934/mbe.2013.10.1561 |
[14] |
Ran Ma, Lu Zhang, Yuzhong Zhang. A best possible algorithm for an online scheduling problem with position-based learning effect. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021144 |
[15] |
Eunice Mureithi. Effects of buoyancy on the lower branch modes on a Blasius boundary layer. Discrete and Continuous Dynamical Systems - B, 2007, 8 (3) : 613-622. doi: 10.3934/dcdsb.2007.8.613 |
[16] |
Alexei Korolev, Gennady Ougolnitsky. Optimal resource allocation in the difference and differential Stackelberg games on marketing networks. Journal of Dynamics and Games, 2020, 7 (2) : 141-162. doi: 10.3934/jdg.2020009 |
[17] |
Jafar Sadeghi, Mojtaba Ghiyasi, Akram Dehnokhalaji. Resource allocation and target setting based on virtual profit improvement. Numerical Algebra, Control and Optimization, 2020, 10 (2) : 127-142. doi: 10.3934/naco.2019043 |
[18] |
Ali Gharouni, Lin Wang. Modeling the spread of bed bug infestation and optimal resource allocation for disinfestation. Mathematical Biosciences & Engineering, 2016, 13 (5) : 969-980. doi: 10.3934/mbe.2016025 |
[19] |
Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044 |
[20] |
John Fogarty. On Noether's bound for polynomial invariants of a finite group. Electronic Research Announcements, 2001, 7: 5-7. |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]