Scheduling jobs with an exponential sum-of-actual-processing-time-based learning effect. (English) Zbl 1205.90138

Summary: We consider single-machine scheduling problems with an exponential sum-of-actual-processing-time-based learning effect. By the exponential sum-of-actual-processing-time-based learning effect, we mean that the processing time of a job is defined by an exponential function of the sum of the actual processing times of the already processed jobs. For the proposed learning model, we show that under certain conditions, the makespan minimization problem, the sum of the \(\theta\)th \((\theta >0)\) powers of completion times minimization problem, and some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem all remain polynomially solvable.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Badiru, A.B., Computational survey of univariate and multivariate learning curve models, IEEE transactions on engineering management, 39, 176-188, (1992)
[2] Biskup, D., A state-of-the-art review on scheduling with learning effects, European journal of operational research, 188, 315-329, (2008) · Zbl 1129.90022
[3] Wang, J.-B.; Ng, C.T.; Cheng, T.C.E.; Liu, L.L., Single-machine scheduling with a time-dependent learning effect, International journal of production economics, 111, 802-811, (2008)
[4] Mosheiov, G., Minimizing total absolute deviation of job completion times: extensions to position-dependent processing times and parallel identical machines, Journal of the operational research society, 59, 1422-1424, (2008) · Zbl 1155.90392
[5] Gordon, V.S.; Potts, C.N.; Strusevich, V.A.; Whitehead, J.D., Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation, Journal of scheduling, 11, 357-370, (2008) · Zbl 1168.90441
[6] Gordon, V.S.; Strusevich, V.A., Single machine scheduling and due date assignment with positionally dependent processing times, European journal of operational research, 198, 57-62, (2009) · Zbl 1163.90781
[7] Wang, J.-B.; Wang, D.; Wang, L.-Y.; Lin, L.; Yin, N.; Wang, W.-W., Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times, Computers & mathematics with applications, 57, 9-16, (2009) · Zbl 1165.90471
[8] Wang, J.-B., Single-machine scheduling with a sum-of-actual-processing-time based learning effect, Journal of the operational research society, 61, 172-177, (2010) · Zbl 1193.90115
[9] Yang, D.-L.; Kuo, W.-H., Single-machine scheduling with an actual time-dependent learning effect, Journal of the operational research society, 58, 1348-1353, (2007) · Zbl 1154.90505
[10] Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of discrete mathematics, 5, 287-326, (1979) · Zbl 0411.90044
[11] Townsend, W., The single machine problem with quadratic penalty function of completion times: a branch-and-bound solution, Management science, 24, 530-534, (1978) · Zbl 0371.90065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.