×
Lu, Yuan-Yuan; Wei, Cai-Min; Wang, Ji-Bo

Several single-machine scheduling problems with general learning effects. (English) Zbl 1254.90073

Appl. Math. Modelling 36, No. 11, 5650-5656 (2012).
Summary: We consider several single-machine scheduling problems with general learning effects. By general learning effects, we mean that the processing time of a job depends not only on its scheduled position, but also on the total normal processing time of the jobs already processed. We show that the scheduling problems of minimization of the makespan, the total completion time and the sum of the \(\theta \)th (\(\theta \leq 0\)) power of job completion times can be solved in polynomial time under the proposed models. We also prove that some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time.

Cited in 7 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68T05 Learning and adaptive systems in artificial intelligence

Keywords:

scheduling; single-machine; learning effect; polynomial time algorithm
PDF BibTeX XML Cite
\textit{Y.-Y. Lu} et al., Appl. Math. Modelling 36, No. 11, 5650--5656 (2012; Zbl 1254.90073)
Full Text: DOI

References:

[1] Biskup, D., Single-machine scheduling with learning considerations, Eur. J. Oper. Res., 115, 173-178 (1999) · Zbl 0946.90025
[2] Cheng, T. C.E.; Wang, G., Single machine scheduling with learning effect considerations, Ann. Oper. Res., 98, 273-290 (2000) · Zbl 0967.68019
[3] Wright, T. P., Factors affecting the cost of airplanes, J. Aeronaut. Sci., 3, 122-128 (1936)
[4] Mosheiov, G., Scheduling problems with a learning effect, Eur. J. Oper. Res., 132, 687-693 (2001) · Zbl 1017.90051
[5] Mosheiov, G., Parallel machine scheduling with a learning effect, J. Oper. Res. Soc., 52, 1165-1169 (2001) · Zbl 1178.90159
[6] Mosheiov, G.; Sidney, J. B., Scheduling with general job-dependent learning curves, Eur. J. Oper. Res., 147, 665-670 (2003) · Zbl 1037.90529
[7] Lee, W.-C.; Wu, C.-C., Minimizing total completion time in a two-machine flowshop with a learning effect, Int. J. Prod. Econ., 88, 85-93 (2004)
[8] Biskup, D.; Simons, D., Common due date scheduling with autonomous and induced learning, Eur. J. Oper. Res., 159, 606-616 (2004) · Zbl 1134.90378
[9] Wang, J.-B.; Xia, Z.-Q., Flow-shop scheduling with a learning effect, J. Oper. Res. Soc., 56, 1325-1330 (2005) · Zbl 1082.90041
[10] Mosheiov, G.; Sidney, J. B., Note on scheduling with general learning curves to minimize the number of tardy jobs, J. Oper. Res. Soc., 56, 110-112 (2005) · Zbl 1122.90356
[11] Kuo, W.-H.; Yang, D.-L., Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect, Eur. J. Oper. Res., 174, 1184-1190 (2006) · Zbl 1103.90341
[12] Kuolamas, C.; Kyparisis, G. J., Single-machine and two-machine flowshop scheduling with general learning functions, Eur. J. Oper. Res., 178, 402-407 (2007) · Zbl 1107.90018
[13] Eren, T.; Guner, E., A bicriteria scheduling with a learning effect: total completion time and total tardiness, INFOR: Infor. Syst. Oper. Res., 45, 75-81 (2007) · Zbl 07683663
[14] Eren, T.; Guner, E., Minimizing total tardiness in a scheduling problem with a learning effect, Appl. Math. Model., 31, 1351-1361 (2007) · Zbl 1145.90021
[15] Wang, J.-B.; Ng, C. T.; Cheng, T. C.E.; Liu, L. L., Single-machine scheduling with a time-dependent learning effect, Int. J. Prod. Econ., 111, 802-811 (2008)
[16] Mosheiov, G.; Sarig, A., A due-window assignment problem with position-dependent processing times, J. Oper. Res. Soc., 59, 997-1003 (2008) · Zbl 1144.90391
[17] Eren, T., A bicriteria parallel machine scheduling with a learning effect of setup and removal times, Appl. Math. Model., 33, 1141-1150 (2009) · Zbl 1168.90436
[18] Gordon, V. S.; Strusevich, V. A., Single machine scheduling and due date assignment with positionally dependent processing times, Eur. J. Oper. Res., 198, 57-62 (2009) · Zbl 1163.90781
[19] Lee, W. C.; Wu, C. C., A note on single-machine group scheduling problems with position-based learning effect, Appl. Math. Model., 33, 2159-2163 (2009) · Zbl 1205.90128
[20] Wu, C. C.; Lee, W. C., Single-machine and flowshop scheduling with a general learning effect model, Comput. Ind. Eng., 56, 1553-1558 (2009)
[21] Cheng, T. C.E.; Cheng, S.-R.; Wu, W.-H.; Hsu, P.-H.; Wu, C.-C., A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations, Comput. Ind. Eng., 60, 534-541 (2011)
[22] Wang, J.-B.; Wang, M.-Z., A revision of machine scheduling problems with a general learning effect, Math. Comput. Model., 53, 330-336 (2011) · Zbl 1211.90093
[23] Wang, J.-B.; Wang, M.-Z., Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects, Ann. Oper. Res., 191, 155-169 (2011) · Zbl 1233.90174
[24] Wu, C.-C.; Yin, Y.; Cheng, S.-R., Some single-machine scheduling problems with a truncation learning effect, Comput. Ind. Eng., 60, 790-795 (2011)
[25] Lai, P. J.; Lee, W. C., Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects, Omega-The Int. J. Manage. Sci., 39, 467-471 (2011)
[26] Bai, J.; Wang, M.-Z.; Wang, J.-B., Single machine scheduling with a general exponential learning effect, Appl. Math. Model., 36, 829-835 (2012) · Zbl 1236.90048
[27] Cheng, T. C.E.; Wu, C. C.; Lee, W. C., Some scheduling problems with deteriorating jobs and learning effects, Comput. Ind. Eng., 54, 972-982 (2008)
[28] Wang, J.-B., Single machine scheduling with a time-dependent learning effect and deteriorating jobs, J. Oper. Res. Soc., 60, 583-586 (2009) · Zbl 1163.90515
[29] Wang, J.-B., Single-machine scheduling with learning effect and deteriorating jobs, Comput. Ind. Eng., 57, 1452-1456 (2009)
[30] Wang, J.-B.; Huang, X.; Wang, X. Y.; Yin, N.; Wang, L. Y., Learning effect and deteriorating jobs in the single machine scheduling problems, Appl. Math. Model., 33, 3848-3853 (2009) · Zbl 1205.90137
[31] Cheng, T. C.E.; Wu, C. C.; Lee, W. C., Scheduling problems with deteriorating jobs and learning effects including proportional setup times, Comput. Ind. Eng., 58, 326-331 (2010)
[32] Wang, J.-B.; Guo, Q., A due-date assignment problem with learning effect and deteriorating jobs, Appl. Math. Model., 34, 309-313 (2010) · Zbl 1185.90099
[33] Bai, J.; Li, Z.-R.; Huang, X., Single-machine group scheduling with general deterioration and learning effects, Appl. Math. Model., 36, 1267-1274 (2012) · Zbl 1243.90055
[34] Bachman, A.; Janiak, A., Scheduling jobs with position-dependent processing times, J. Oper. Res. Soc., 55, 257-264 (2004) · Zbl 1095.90033
[35] Biskup, D., A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 188, 315-329 (2008) · Zbl 1129.90022
[36] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[37] Townsend, W., The single machine problem with quadratic penalty function of completion times: a branch-and-bound solution, Manage. Sci., 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.