Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author

    * 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).
Abstract Full Text(HTML) Figure(0) / Table(5) Related Papers Cited by
  • 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.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Data of Example 1

     | Show Table
    DownLoad: CSV

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

    ${j\backslash r}$${1}$${2}$${3}$${4}$${5}$${6}$
     | Show Table
    DownLoad: CSV

    Table 3.  Data of Example 2

     | Show Table
    DownLoad: CSV

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

    ${j\backslash r}$${1}$${2}$${3}$${4}$${5}$${6}$
    The bold numbers are the optimal solution
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV
  • [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. BaiZ.-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. BaiM.-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. ChengS.-R. ChengW.-H. WuP.-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. ChengW.-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. GrahamE. L. LawlerJ. 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. GuoW. 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. HardyJ. E. Littlewood and  G. PolyaInequalities, 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. LiM.-L. LuoW.-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. NiuJ. 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. WangM.-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. WangJ.-B. WangJ. 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. WangM.-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. WangX.-Y. WangL.-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. WangZ. ZhouX. ZhangP. 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. WeiJ.-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. WuY. 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. WuY. 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. WuY. YinW.-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. WuY. YinW.-H. WuC.-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. XuK. 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. XuL. WanA. 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. YangT. 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. YinT. C. E. ChengL. WanC.-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. 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 Operation Research Society, 65 (2014), 1-13. 
    [40] N. YinL. 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. ZhaoC.-J. HsuW.-H. WuS.-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. 
  • 加载中



Article Metrics

HTML views(739) PDF downloads(355) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint