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

Ji-Bo Wang; Mengqi Liu; Na Yin; Ping Ji

doi:10.3934/jimo.2016060

Article Contents

2017, Volume 13, Issue 2: 1025-1039. Doi: 10.3934/jimo.2016060

This issue Previous Article A superlinearly convergent hybrid algorithm for solving nonlinear programming Next Article A multi-objective integrated model for closed-loop supply chain configuration and supplier selection considering uncertain demand and different performance levels

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

1.
School of Science, Shenyang Aerospace University, Shenyang 110136, China
2.
Business School, Hunan University, Changsha 410082, Hunan, China
3.
Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China

* Corresponding author
* Corresponding author

Received: September 30, 2015

Revised: May 31, 2016

Published: August 2017

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

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| 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

Related Papers

Cited by

References

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