\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

  • *Corresponding author

    *Corresponding author

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
  • 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.

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

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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 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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV
  • [1] A. AzzouzM. 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. HardyJ.-E. Littlewood and  G. PolyaInequalities, 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. HuangM.-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. LiangM. LiuY.-B. FengJ.-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. LiuX. 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. LiuJ.-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. LiuB. NiuM. XingL. 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. LiuJ. 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. LuJ.-B. WangP. 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. LvS.-W. LuoJ. XueJ.-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. SunX. 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. WangM. GaoJ.-J. WangL. 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. WangX. 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. WangY. 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. WangW. LiuL. LiP. 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. WangF. 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. WangL. LiuJ.-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. WangM. LiuN. 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. WangD.-Y. LvJ. XuP. 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. WangM.-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. WangB. 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. WuW.-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. YinT. C. E. ChengC.-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. ZhuL.-Y. SunF. Chu and M. Liu, Single-machine group scheduling with resource allocation and learning effect, Computers & Industrial Engineering, 60 (2011), 148-157. 
  • 加载中

Tables(3)

SHARE

Article Metrics

HTML views(978) PDF downloads(224) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return