doi: 10.3934/jimo.2022011
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.

Resource allocation scheduling with deteriorating jobs and position-dependent workloads

1. 

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

2. 

Department of Sport Education and Humanity, Nanjing Sport Institute, Nanjing 210014, China

*Corresponding author

Received  September 2021 Early access January 2022

Fund Project: This Work Was Supported by LiaoNing Revitalization Talents Program (grant no. XLYC2002017)

In this study, we consider the resource allocation scheduling with a deterioration effect and position-dependent workloads concurrently on a single machine. The scheduler needs to find the optimal sequence and the optimal resource allocation such that a cost function is minimized. First, the focus is on minimizing the linear weighted sum of the schedule cost and resource consumption cost. Second problem is to minimize the schedule cost subject to an upper bound on the resource consumption cost. Third problem is to minimize the resource consumption cost subject to an upper bound on the schedule cost. Last problem is to find Pareto-optimal solutions for schedule cost and resource consumption cost. We proved that these problems remain polynomially solvable respectively.

Citation: 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, doi: 10.3934/jimo.2022011
References:
[1]

U. B. Bagchi, Simultaneous minimization of mean and variation of flow-time and waiting time in single machine systems, Oper. Res., 37 (1989), 118-125.  doi: 10.1287/opre.37.1.118.

[2]

S. Gawiejnowicz, Models and Algorithms of Time-Dependent Scheduling, 2$^{nd}$ edition, Monographs in Theoretical Computer Science. An EATCS Series. Springer, Berlin, 2020.

[3]

R. L. GrahamE. L. LawlerJ. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math., 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.

[4]

G. H. Hardy, J. E. Littlewood and G. Polya, Inequalities, Cambridge University Press, 1967.

[5]

H.-Y. HeM. Liu and J.-B. Wang, Resource constrained scheduling with general truncated job-dependent learning effect, J. Comb. Optim., 33 (2017), 626-644.  doi: 10.1007/s10878-015-9984-5.

[6]

X. Huang, Bicriterion scheduling with group technology and deterioration effect, J. Appl. Math. Comput., 60 (2019), 455-464.  doi: 10.1007/s12190-018-01222-1.

[7]

X. Huang, N. Yin, W.-W. Liu and J.-B. Wang, Common due window assignment scheduling with proportional linear deterioration effects, Asia-Pac. J. Oper. Res., 37 (2020), 1950031, 15 pp. doi: 10.1142/S0217595919500313.

[8]

J. J. Kanet, Minimizing variation of flow time in single machine systems, Management Science, 27 (1981), 1453-1459. 

[9]

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, Eng. Optim., 52 (2020), 1184-1197.  doi: 10.1080/0305215X.2019.1638920.

[10]

W.-W. Liu and C. Jiang, Flow shop resource allocation scheduling with due date assignment, learning effect and position-dependent weights, Asia-Pac. J. Oper. Res., 37 (2020), 2050014, 27 pp. doi: 10.1142/S0217595920500141.

[11]

W.-W. LiuY. Yao and C. Jiang, Single machine resource allocation scheduling with due-date assignment, deterioration effect and position-dependent weights, Eng. Optim., 52 (2020), 701-714.  doi: 10.1080/0305215X.2019.1608980.

[12]

Y.-Y. Lu and J.-Y. Liu, A note on resource allocation scheduling with position-dependent workloads, Eng. Optim., 50 (2018), 1810-1827.  doi: 10.1080/0305215X.2017.1414207.

[13]

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, Eng. Optim., 49 (2017), 1621-1632.  doi: 10.1080/0305215X.2016.1265305.

[14]

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. 

[15]

D. Oron, Scheduling controllable processing time jobs in a deteriorating environment, Journal of the Operational Research Society, 64 (2014), 49-56. 

[16]

D. Oron, Scheduling controllable processing time jobs with position-dependent workloads, International Journal of Production Economics, 173 (2016), 153-160. 

[17]

J. Qian and H. Han, The due date assignment scheduling problem with the deteriorating jobs and delivery time, Journal of Applied Mathematics and Computing, 2021. doi: 10.1007/s12190-021-01607-9.

[18]

D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times, Discrete Appl. Math., 155 (2007), 1643-1666.  doi: 10.1016/j.dam.2007.02.003.

[19]

X. Sun and X.-N. Geng, Single-machine scheduling with deteriorating effects and machine maintenance, International Journal of Production Research, 57 (2019), 3186-3199. 

[20]

V. T'kindt and J.-C. Billaut, Multicriteria Scheduling: Theory, Models and Algorithms, 2$^{nd}$ edition, Springer-Verlag Berlin Heidelberg, 2006.

[21]

D. Wang and Z. Li, Bicriterion scheduling with a negotiable common due window and resource- dependent processing times, Inform. Sci., 478 (2019), 258-274.  doi: 10.1016/j.ins.2018.11.023.

[22]

D. WangY. Yin and M. Liu, Bicriterion scheduling problems involving job rejection, controllable processing times and rate-modifying activity, International Journal of Production Research, 54 (2016), 3691-3705. 

[23]

J.-B. Wang and X.-X. Liang, Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint, Eng. Optim., 51 (2019), 231-246.  doi: 10.1080/0305215X.2018.1454442.

[24]

J.-B. WangM. LiuN. Yin and P. Ji, Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects, J. Ind. Manag. Optim., 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, Int. Trans. Oper. Res., 28 (2021), 1573-1593.  doi: 10.1111/itor.12888.

[26]

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. 

[27]

J.-B. Wang and M.-Z. Wang, Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time, Comput. Oper. Res., 39 (2012), 492-497.  doi: 10.1016/j.cor.2011.05.026.

[28]

J.-B. Wang, B. Zhang and H. He, A unified analysis for scheduling problems with variable processing times, Journal of Industrial and Management Optimization. doi: 10.3934/jimo.2021008.

[29]

X.-R. Wang and J.-J. Wang, Single-machine scheduling with convex resource dependent processing times and deteriorating jobs, Appl. Math. Model., 37 (2013), 2388-2393.  doi: 10.1016/j.apm.2012.05.025.

[30]

C.-M. WeiJ.-B. Wang and P. Ji, Single-machine scheduling with time-and-resource-dependent processing times, Appl. Math. Model., 62 (2012), 792-798.  doi: 10.1016/j.apm.2011.07.005.

[31]

S. Zhao, Resource allocation flowshop scheduling with learning effect and slack due window assignment, J. Ind. Manag. Optim., 17 (2021), 2817-2835.  doi: 10.3934/jimo.2020096.

show all references

References:
[1]

U. B. Bagchi, Simultaneous minimization of mean and variation of flow-time and waiting time in single machine systems, Oper. Res., 37 (1989), 118-125.  doi: 10.1287/opre.37.1.118.

[2]

S. Gawiejnowicz, Models and Algorithms of Time-Dependent Scheduling, 2$^{nd}$ edition, Monographs in Theoretical Computer Science. An EATCS Series. Springer, Berlin, 2020.

[3]

R. L. GrahamE. L. LawlerJ. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math., 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.

[4]

G. H. Hardy, J. E. Littlewood and G. Polya, Inequalities, Cambridge University Press, 1967.

[5]

H.-Y. HeM. Liu and J.-B. Wang, Resource constrained scheduling with general truncated job-dependent learning effect, J. Comb. Optim., 33 (2017), 626-644.  doi: 10.1007/s10878-015-9984-5.

[6]

X. Huang, Bicriterion scheduling with group technology and deterioration effect, J. Appl. Math. Comput., 60 (2019), 455-464.  doi: 10.1007/s12190-018-01222-1.

[7]

X. Huang, N. Yin, W.-W. Liu and J.-B. Wang, Common due window assignment scheduling with proportional linear deterioration effects, Asia-Pac. J. Oper. Res., 37 (2020), 1950031, 15 pp. doi: 10.1142/S0217595919500313.

[8]

J. J. Kanet, Minimizing variation of flow time in single machine systems, Management Science, 27 (1981), 1453-1459. 

[9]

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, Eng. Optim., 52 (2020), 1184-1197.  doi: 10.1080/0305215X.2019.1638920.

[10]

W.-W. Liu and C. Jiang, Flow shop resource allocation scheduling with due date assignment, learning effect and position-dependent weights, Asia-Pac. J. Oper. Res., 37 (2020), 2050014, 27 pp. doi: 10.1142/S0217595920500141.

[11]

W.-W. LiuY. Yao and C. Jiang, Single machine resource allocation scheduling with due-date assignment, deterioration effect and position-dependent weights, Eng. Optim., 52 (2020), 701-714.  doi: 10.1080/0305215X.2019.1608980.

[12]

Y.-Y. Lu and J.-Y. Liu, A note on resource allocation scheduling with position-dependent workloads, Eng. Optim., 50 (2018), 1810-1827.  doi: 10.1080/0305215X.2017.1414207.

[13]

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, Eng. Optim., 49 (2017), 1621-1632.  doi: 10.1080/0305215X.2016.1265305.

[14]

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. 

[15]

D. Oron, Scheduling controllable processing time jobs in a deteriorating environment, Journal of the Operational Research Society, 64 (2014), 49-56. 

[16]

D. Oron, Scheduling controllable processing time jobs with position-dependent workloads, International Journal of Production Economics, 173 (2016), 153-160. 

[17]

J. Qian and H. Han, The due date assignment scheduling problem with the deteriorating jobs and delivery time, Journal of Applied Mathematics and Computing, 2021. doi: 10.1007/s12190-021-01607-9.

[18]

D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times, Discrete Appl. Math., 155 (2007), 1643-1666.  doi: 10.1016/j.dam.2007.02.003.

[19]

X. Sun and X.-N. Geng, Single-machine scheduling with deteriorating effects and machine maintenance, International Journal of Production Research, 57 (2019), 3186-3199. 

[20]

V. T'kindt and J.-C. Billaut, Multicriteria Scheduling: Theory, Models and Algorithms, 2$^{nd}$ edition, Springer-Verlag Berlin Heidelberg, 2006.

[21]

D. Wang and Z. Li, Bicriterion scheduling with a negotiable common due window and resource- dependent processing times, Inform. Sci., 478 (2019), 258-274.  doi: 10.1016/j.ins.2018.11.023.

[22]

D. WangY. Yin and M. Liu, Bicriterion scheduling problems involving job rejection, controllable processing times and rate-modifying activity, International Journal of Production Research, 54 (2016), 3691-3705. 

[23]

J.-B. Wang and X.-X. Liang, Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint, Eng. Optim., 51 (2019), 231-246.  doi: 10.1080/0305215X.2018.1454442.

[24]

J.-B. WangM. LiuN. Yin and P. Ji, Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects, J. Ind. Manag. Optim., 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, Int. Trans. Oper. Res., 28 (2021), 1573-1593.  doi: 10.1111/itor.12888.

[26]

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. 

[27]

J.-B. Wang and M.-Z. Wang, Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time, Comput. Oper. Res., 39 (2012), 492-497.  doi: 10.1016/j.cor.2011.05.026.

[28]

J.-B. Wang, B. Zhang and H. He, A unified analysis for scheduling problems with variable processing times, Journal of Industrial and Management Optimization. doi: 10.3934/jimo.2021008.

[29]

X.-R. Wang and J.-J. Wang, Single-machine scheduling with convex resource dependent processing times and deteriorating jobs, Appl. Math. Model., 37 (2013), 2388-2393.  doi: 10.1016/j.apm.2012.05.025.

[30]

C.-M. WeiJ.-B. Wang and P. Ji, Single-machine scheduling with time-and-resource-dependent processing times, Appl. Math. Model., 62 (2012), 792-798.  doi: 10.1016/j.apm.2011.07.005.

[31]

S. Zhao, Resource allocation flowshop scheduling with learning effect and slack due window assignment, J. Ind. Manag. Optim., 17 (2021), 2817-2835.  doi: 10.3934/jimo.2020096.

Table 1.  Values of $ w_{j, r} $
$ j $ $ \setminus $ $ r $ $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $
$ 1 $ $ 4 $ $ 3 $ $ 10 $ $ 7 $ $ 5 $
$ 2 $ $ 3 $ $ 6 $ $ 5 $ $ 3 $ $ 4 $
$ 3 $ $ 8 $ $ 9 $ $ 7 $ $ 12 $ $ 2 $
$ 4 $ $ 15 $ $ 11 $ $ 12 $ $ 13 $ $ 4 $
$ 5 $ $ 12 $ $ 4 $ $ 5 $ $ 4 $ $ 3 $
$ j $ $ \setminus $ $ r $ $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $
$ 1 $ $ 4 $ $ 3 $ $ 10 $ $ 7 $ $ 5 $
$ 2 $ $ 3 $ $ 6 $ $ 5 $ $ 3 $ $ 4 $
$ 3 $ $ 8 $ $ 9 $ $ 7 $ $ 12 $ $ 2 $
$ 4 $ $ 15 $ $ 11 $ $ 12 $ $ 13 $ $ 4 $
$ 5 $ $ 12 $ $ 4 $ $ 5 $ $ 4 $ $ 3 $
Table 2.  Values of $ \left(v_{j}w_{j, r}\right)^{\frac{\eta}{\eta+1}} \left(\Xi_{r}\right)^{\frac{1}{\eta+1}} $
$ j $ $ \setminus $ $ r $ $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $
$ 1 $ 36.9383 21.2221 33.0193 17.4264 8.7721
$ 2 $ 48.4029 53.4764 33.0193 15.7244 12.0000
$ 3 $ 82.4257 62.0539 36.5931 35.0882 6.6943
$ 4 $ 108.0082 61.1311 45.1697 31.8955 9.1577
$ 5 $ 135.1685 45.2272 36.5931 21.1105 10.9779
$ j $ $ \setminus $ $ r $ $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $
$ 1 $ 36.9383 21.2221 33.0193 17.4264 8.7721
$ 2 $ 48.4029 53.4764 33.0193 15.7244 12.0000
$ 3 $ 82.4257 62.0539 36.5931 35.0882 6.6943
$ 4 $ 108.0082 61.1311 45.1697 31.8955 9.1577
$ 5 $ 135.1685 45.2272 36.5931 21.1105 10.9779
[1]

Si-Han Wang, Dan-Yang Lv, Ji-Bo Wang. Research on position-dependent weights scheduling with delivery times and truncated sum-of-processing-times-based learning effect. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022066

[2]

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

[3]

Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial and Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691

[4]

Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial and Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076

[5]

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, 2022  doi: 10.3934/jimo.2022091

[6]

Sachiko Ishida. Global existence and boundedness for chemotaxis-Navier-Stokes systems with position-dependent sensitivity in 2D bounded domains. Discrete and Continuous Dynamical Systems, 2015, 35 (8) : 3463-3482. doi: 10.3934/dcds.2015.35.3463

[7]

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

[8]

Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[9]

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

[10]

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

[11]

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

[12]

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

[13]

Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021190

[14]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044

[15]

Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial and Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040

[16]

Chaoming Hu, Xiaofei Qian, Shaojun Lu, Xinbao Liu, Panos M Pardalos. Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021142

[17]

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

[18]

Wael Bahsoun, Christopher Bose, Anthony Quas. Deterministic representation for position dependent random maps. Discrete and Continuous Dynamical Systems, 2008, 22 (3) : 529-540. doi: 10.3934/dcds.2008.22.529

[19]

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

[20]

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

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (248)
  • HTML views (121)
  • Cited by (0)

Other articles
by authors

[Back to Top]