Article Contents
Article Contents

# Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects

• * Corresponding author
The work described in this paper was partially supported by the grant from The Hong Kong Polytechnic University (PolyU projects G-YBFE and 4-BCBJ) and the National Natural Science Foundation of China (Grant Nos. 71471120 and 71471057).
• In this paper, we consider single machine scheduling problems with controllable processing time (resource allocation), truncated job-dependent learning and deterioration effects. The goal is to find the optimal sequence of jobs and the optimal resource allocation separately for minimizing a cost function containing makespan (total completion time, total absolute differences in completion times) and/or total resource cost. For two different processing time functions, i.e., a linear and a convex function of the amount of a common continuously divisible resource allocated to the job, we solve them in polynomial time respectively.

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

 Citation:

• Table 1.  Data of Example 1

 $J_{j}$ $J_{1}$ $J_{2}$ $J_{3}$ $J_{4}$ $J_{5}$ $J_{6}$ $p_{j}$ 10 8 11 18 9 16 $\beta_{j}$ 2 1 3 2 3 4 $\bar{u}_{j}$ 3 2 3 1 2 2 $v_{j}$ 10 8 12 11 14 9 $a_{j}$ -0.25 -0.15 -0.2 -0.1 -0.3 -0.25

Table 2.  Values of $\Lambda_{jr}$

 ${j\backslash r}$ ${1}$ ${2}$ ${3}$ ${4}$ ${5}$ ${6}$ $1$ 57.2076 43.3110 32.7497 22.2915 14.3500 7.0000 $2$ 54.4152 39.8396 29.2421 20.4850 12.8824 6.1146 $3$ 49.6038 39.1831 35.2680 26.2806 16.3438 7.7000 $4$ 119.8304 92.7490 69.5101 49.3994 31.4144 15.0473 $5$ 48.4057 35.2400 27.8993 19.8607 12.9150 6.3000 $6$ 72.4152 48.1385 35.9187 28.4465 22.9600 11.2000

Table 3.  Data of Example 2

 $J_{j}$ $J_{1}$ $J_{2}$ $J_{3}$ $J_{4}$ $J_{5}$ $J_{6}$ $p_{j}$ 10 8 11 18 9 1 $v_{j}$ 10 8 12 11 14 9 $a_{j}$ -0.25 -0.15 -0.2 -0.1 -0.3 -0.25

Table 4.  Values of $\Theta_{jr}$

 ${j\backslash r}$ ${1}$ ${2}$ ${3}$ ${4}$ ${5}$ ${6}$ $1$ 77.1456 64.1292 55.1751 47.3852 40.7772 32.0996 $2$ 57.2925 49.8783 44.0898 38.5982 32.7021 25.2778 $3$ 92.8312 78.9720 68.8700 59.7165 50.2195 38.6263 $4$ 121.6433 108.3767 97.1029 85.8274 73.2596 56.9729 $5$ 89.9964 73.1030 62.0516 54.9075 47.5698 37.4467 $6$ 98.3754 81.7770 70.3588 60.4252 51.9987 40.9331 The bold numbers are the optimal solution

Table 5.  Main results of this paper ($\rho\in\{C_{\max},\sum C_j, TADC\}$)

 $1|p_{jr}^A(t,u_j)=p_j\max\left\{r^{a_j},b\right\}+c t-\theta_{j} u_{j}|\delta_1 \rho+\delta_2 \sum_{j=1}^{n}v_{j}u_{j}$ $O(n^3)$ Theorem 3.3 $1| p_{jr}^A(t,u_j)= \left(\frac{p_j\max\left\{r^{a_j},b\right\}}{u_j}\right)^l +ct|\delta_1\rho+\delta_2 \sum_{j=1}^{n}v_{j}u_{j}$ $O(n^3)$ Theorem 4.4 $1| p_{jr}^A(t,u_j)= \left(\frac{p_j\max\left\{r^{a},b\right\}}{u_j}\right)^l +ct|\delta_1\rho+\delta_2 \sum_{j=1}^{n}v_{j}u_{j}$ $O(n\log n)$ Theorem 4.6 $1| p_{jr}^A(t,u_j)= \left(\frac{p_j\max\left\{r^{a_j},b\right\}}{u_j}\right)^l +ct,\sum_{j=1}^{n}u_{j}\leq U |\rho$ $O(n^3)$ Theorem 4.9 $1| p_{jr}^A(t,u_j)= \left(\frac{p_j\max\left\{r^{a},b\right\}}{u_j}\right)^l +ct,\sum_{j=1}^{n}u_{j}\leq U|\rho$ $O(n\log n)$ Theorem 4.10 $1| p_{jr}^A(t,u_j)= \left(\frac{p_j\max\left\{r^{a_j},b\right\}}{u_j}\right)^l +ct,\rho\leq R|\sum_{j=1}^{n}u_{j}$ $O(n^3)$ Theorem 4.13 $1| p_{jr}^A(t,u_j)= \left(\frac{p_j\max\left\{r^{a},b\right\}}{u_j}\right)^l +ct,\rho\leq R| \sum_{j=1}^{n}u_{j}$ $O(n\log n)$ Theorem 4.14 $1|p_{j}^A= \left(\frac{p_j\max\left\{r^{a_j},b\right\}}{u_j}\right)^l +c t|(\rho,\sum_{j=1}^{n}u_{j})$ $O(n^3)$ Theorem 4.15 $1|p_{j}^A= \left(\frac{p_j\max\left\{r^{a},b\right\}}{u_j}\right)^l +c t|(\rho,\sum_{j=1}^{n}u_{j})$ $O(n\log n)$ Theorem 4.16
•  [1] A. Bachman, A. G. Janiak, I. B. Alidaee and N. K. Womer, Scheduling deteriorating jobs dependent on resources for the makespan minimization, In Operations Research Proceedings 2000: Selected Papers of the Symposium on Operations Research (OR 2000), Dresden: Springer, (2001), 29-34. [2] J. Bai, Z.-R. Li and X. Huang, Single-machine group scheduling with general deterioration and learning effects, Applied Mathematical Modelling, 36 (2012), 1267-1274.  doi: 10.1016/j.apm.2011.07.068. [3] J. Bai, M.-Z. Wang and J.-B. Wang, Single machine scheduling with a general exponential learning effect, Applied Mathematical Modelling, 36 (2012), 829-835.  doi: 10.1016/j.apm.2011.07.002. [4] D. Biskup, Single-machine scheduling with learning considerations, European Journal of Operational Research, 115 (1999), 173-178. [5] D. Biskup, A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188 (2008), 315-329.  doi: 10.1016/j.ejor.2007.05.040. [6] T. C. E. Cheng, S.-R. Cheng, W.-H. Wu, P.-H. Hsu and C.-C. Wu, A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations, Computers & Industrial Engineering, 60 (2011), 534-541. [7] T. C. E. Cheng, W.-H. Kuo and D.-L. Yang, Scheduling with a position-weighted learning effect based on sum-of-logarithm-processing-times and job position, Information Sciences, 221 (2013), 490-500.  doi: 10.1016/j.ins.2012.09.001. [8] S. Gawiejnowicz, Time-Dependent Scheduling, Springer-Verlag Berlin Heidelberg, 2008. [9] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X. [10] P. Guo, W. Cheng and Y. Wang, A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs, Journal of Industrial and Management Optimization, 10 (2014), 1071-1090.  doi: 10.3934/jimo.2014.10.1071. [11] G. H. Hardy,  J. E. Littlewood and  G. Polya,  Inequalities, Cambridge University Press, Cambridge, 1976. [12] H. Hoogeveen, Multicriteria scheduling, European Journal of Operational Research, 167 (2005), 592-623.  doi: 10.1016/j.ejor.2004.07.011. [13] I. Kacem and E. Levner, An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs, Journal of Industrial and Management Optimization, 12 (2016), 811-817.  doi: 10.3934/jimo.2016.12.811. [14] J. J. Kanet, Minimizing variation of flow time in single machine systems, Management Science, 27 (1981), 1453-1459. [15] G. Li, M.-L. Luo, W.-J. Zhang and X.-Y. Wang, Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation, International Journal of Production Research, 54 (2015), 1228-1241. [16] G. Mosheiov and J. B. Sidney, Scheduling with general job-dependent learning curves, European Journal of Operational Research, 147 (2003), 665-670.  doi: 10.1016/S0377-2217(02)00358-2. [17] Y.-P. Niu, J. Wang and N. Yin, Scheduling problems with effects of deterioration and truncated job-dependent learning, Journal of Applied Mathematics and Computing, 47 (2015), 315-325.  doi: 10.1007/s12190-014-0777-2. [18] J. Qian and G. Steiner, Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine, European Journal of Operational Research, 225 (2013), 547-551.  doi: 10.1016/j.ejor.2012.09.013. [19] 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. [20] J.-B. Wang and M.-Z. Wang, Minimizing makespan in three-machine flow shops with deteriorating jobs, Computers & Operations Research, 30 (2013), 1350022, 14 pp.  doi: 10.1142/S021759591350022X. [21] X.-R. Wang and J.-J. Wang, Single-machine scheduling with convex resource dependent processing times and deteriorating jobs, Applied Mathematical Modelling, 37 (2013), 2388-2393.  doi: 10.1016/j.apm.2012.05.025. [22] J.-B. Wang, M.-Z. Wang and P. Ji, Scheduling jobs with processing times dependent on position, starting time and allotted resource, Asia-Pacific Journal of Operational Research, 29 (2012), 1250030 (15 pages).  doi: 10.1142/S0217595912500303. [23] X.-R. Wang, J.-B. Wang, J. Jin and P. Ji, Single machine scheduling with truncated job-dependent learning effect, Optimization Letters, 8 (2014), 669-677.  doi: 10.1007/s11590-012-0579-0. [24] D. Wang, M.-Z. Wang and J.-B. Wang, Single-machine scheduling with learning effect and resource-dependent processing times, Computers & Industrial Engineering, 59 (2010), 458-462. [25] J.-B. Wang, X.-Y. Wang, L.-H. Sun and L.-Y. Sun, Scheduling jobs with truncated exponential learning functions, Optimization Letters, 7 (2013), 1857-1873.  doi: 10.1007/s11590-011-0433-9. [26] X.-Y. Wang, Z. Zhou, X. Zhang, P. Ji and J.-B. Wang, Several flow shop scheduling problems with truncated position-based learning effect, Computers & Operations Research, 40 (2013), 2906-2929.  doi: 10.1016/j.cor.2013.07.001. [27] C.-M. Wei, J.-B. Wang and P. Ji, Single-machine scheduling with time-and-resource-dependent processing times, Applied Mathematical Modelling, 36 (2012), 792-798.  doi: 10.1016/j.apm.2011.07.005. [28] C.-C. Wu, Y. Yin and S.-R. Cheng, Some single-machine scheduling problems with a truncation learning effect, Computers & Industrial Engineering, 60 (2011), 790-795. [29] C.-C. Wu, Y. Yin and S.-R. Cheng, Single-machine and two-machine flowshop scheduling problems with truncated position-based learning functions, Journal of the Operation Research Society, 64 (2013), 147-156. [30] C.-C. Wu, Y. Yin, W.-H. Wu and S.-R. Cheng, Some polynomial solvable single-machine scheduling problems with a truncation sum-of-processing-times based learning effect, European Journal of Industrial Engineering, 6 (2012), 441-453. [31] W.-H. Wu, Y. Yin, W.-H. Wu, C.-C. Wu and P.-H. Hsu, A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents, Journal of Industrial and Management Optimization, 10 (2014), 591-611.  doi: 10.3934/jimo.2014.10.591. [32] D. Xu, K. Sun and H. Li, Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan, Computers & Operations Research, 35 (2008), 1344-1349.  doi: 10.1016/j.cor.2006.08.015. [33] D. Xu, L. Wan, A. Liu and D.-L. Yang, Single machine total completion time scheduling problem with workload-dependent maintenance duration, Omega-The International Journal of Management Science, 52 (2015), 101-106. [34] D.-L. Yang, T. C. E. Cheng and S.-J. Yang, Parallel-machine scheduling with controllable processing times and rate-modifying activities to minimise total cost involving total completion time and job compressions, International Journal of Production Research, 52 (2014), 1133-1141. [35] D.-L. Yang and W.-H. Kuo, Some scheduling problems with deteriorating jobs and learning effects, Computers & Industrial Engineering, 58 (2010), 25-28. [36] Y. Yin, S. -R. Cheng, J. Y. Chiang, J. C. H. Chen, X. Mao and C. -C. Wu, Scheduling problems with due date assignment, Discrete Dynamics in Nature and Society, 2015 (2015), Article ID 683269 (2 pages). [37] Y. Yin, T. C. E. Cheng, L. Wan, C.-C. Wu and J. Liu, Two-agent singlemachine scheduling with deteriorating jobs, Computers & Industrial Engineering, 81 (2015), 177-185. [38] Y. Yin, T. C. E. Cheng and C. -C. Wu, Scheduling with time-dependent processing times, Mathematical Problems in Engineering, 2015 (2015), Article ID 367585 (2 pages). [39] 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 Operation Research Society, 65 (2014), 1-13. [40] N. Yin, L. Kang and X.-Y. Wang, Single-machine group scheduling with processing times dependent on position, starting time and allotted resource, Applied Mathematical Modelling, 38 (2014), 4602-4613.  doi: 10.1016/j.apm.2014.03.014. [41] Y. Yin, D. -J. Wang, T. C. E. Cheng and C. -C. Wu, Bi-criterion single-machine scheduling and due window assignment with common flow allowances and resource-dependent processing times Journal of the Operation Research Society, (2016). doi: 10.1057/jors.2016.14. [42] C. Zhao, C.-J. Hsu, W.-H. Wu, S.-R. Cheng and C.-C. Wu, Note on a unified approach to the single-machine scheduling problem with a deterioration effect and convex resource allocation, Journal of Manufacturing Systems, 38 (2016), 134-140.

Tables(5)