American Institute of Mathematical Sciences

Advanced
  • 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
doi: 10.3934/jimo.2022091
Online First

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

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

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

*Corresponding author

Received  March 2022 Revised  April 2022 Early access June 2022

Fund Project: 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)

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: Scheduling, learning effects, resource allocation, group technology, branch-and-bound algorithm.
Mathematics Subject Classification: Primary: 90B35; Secondary: 90C26.
Citation: Jia-Xuan Yan, Na Ren, Hong-Bin Bei, Han Bao, Ji-Bo Wang. Study on resource allocation scheduling problem with learning factors and group technology. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2022091
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. 

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 ) $
Table Options

Download as excel

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 ) $
Table 2.  Results of Algorithms for ai ~ (−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
Table Options

Download as excel

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
Table 3.  Results of Algorithms for ai ~ (−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
Table Options

Download as excel

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
[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

  • PDF downloads (68)
  • HTML views (34)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy