Shen, Lixin; Wu, Yu-Bin Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects. (English) Zbl 1426.90139 Appl. Math. Modelling 37, No. 7, 5444-5451 (2013). Summary: This paper studies the single machine past-sequence-dependent (p-s-d) delivery times scheduling with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects we mean that the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. We consider the following objective functions: the makespan, the total completion time, the sum of the \({\theta}\)th \(({\theta}\geqslant 0)\) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of minimization of the makespan, the total completion time, the sum of the \({\theta}\)th \(({\theta}\geqslant 0)\) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness minimization problem, the maximum tardiness minimization problem and the total tardiness minimization problem can be solved in polynomial time under certain conditions. Cited in 9 Documents MSC: 90B35 Deterministic scheduling theory in operations research Keywords:scheduling; single machine; learning effect; delivery times PDFBibTeX XMLCite \textit{L. Shen} and \textit{Y.-B. Wu}, Appl. Math. Modelling 37, No. 7, 5444--5451 (2013; Zbl 1426.90139) Full Text: DOI References: [1] Badiru, A. B., Computational survey of univariate and multivariate learning curve models, IEEE Trans. Eng. Manage., 39, 176-188, (1992) [2] Biskup, D., A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 188, 315-329, (2008) · Zbl 1129.90022 [3] Janiak, A.; Krysiak, T.; Trela, R., Scheduling problems with learning and ageing effects: a survey, Decision Making Manufactur. Serv., 5, 19-36, (2011) · Zbl 1245.90031 [4] Biskup, D., Single-machine scheduling with learning considerations, Eur. J. Oper. Res., 115, 173-178, (1999) · Zbl 0946.90025 [5] Janiak, A.; Bachman, A., Scheduling jobs with position-dependent processing times, J. Oper. Res. Soc., 55, 257-264, (2004) · Zbl 1095.90033 [6] 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 [7] Koulamas, 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 [8] Cheng, T. C.E.; Wu, C.-C.; Lee, W.-C., Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects, Info. Sci., 178, 2476-2487, (2008) · Zbl 1172.90397 [9] 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, Comput. Math. Appl., 57, 9-16, (2009) · Zbl 1165.90471 [10] A. Janiak, A. Śnieżyk, Minimizing the maximum lateness of jobs with the aging effect, in: Proc. 12th IEEE Int. Conf. on Methods and Models in Automation and Robotics, Miedzyzdroje, Poland, 29 August-1 September, 2005, pp. 1067-1071. [11] A. Janiak, A. Śnieżyk, Single processor scheduling with the linear aging effect, ready times and the makespan criterion, in: Proc. 12th IEEE Int. Conf. Methods and Models in Automation and Robotics, Miedzyzdroje, Poland, 29 August-1 September, 2005, pp. 1073-1077. [12] Mosheiov, G., Minimizing total absolute deviation of job completion times: extensions to position-dependent processing times and parallel identical machines, J. Oper. Res. Soc., 59, 1422-1424, (2008) · Zbl 1155.90392 [13] Wang, J.-B.; Ng, C. T.; Cheng, T. C.E.; Liu, L. L., Single-machine scheduling with a time-dependent learning effect, Int. J. Produc. Econ., 111, 802-811, (2008) [14] Wang, J.-B., Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect, Comput. Indust. Eng., 55, 584-591, (2008) [15] Wu, C. C.; Lee, W. C., Single-machine scheduling problems with a learning effect, Appl. Math. Model., 32, 1191-1197, (2008) · Zbl 1172.90415 [16] Wu, C. C.; Lee, W. C., Single-machine and flowshop scheduling with a general learning effect model, Comput. Indust. Eng., 56, 1553-1558, (2009) [17] Lee, W.-C.; Wu, C.-C., Some single-machine and m-machine flowshop scheduling problems with learning considerations, Info. Sci., 179, 3885-3892, (2009) · Zbl 1179.90141 [18] 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 [19] Yin, Y.; Xu, D.; Sun, K.; Li, H., Some scheduling problems with general position-dependent and time-dependent learning effects, Info. Sci., 179, 2416-2425, (2009) · Zbl 1166.90342 [20] Cheng, T. C.E.; Wu, C.-C.; Lee, W.-C., Scheduling problems with deteriorating jobs and learning effects including proportional setup times, Comput. Indust. Eng., 58, 326-331, (2010) [21] 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 [22] Wang, J.-B., Single-machine scheduling with a sum-of-actual-processing-time based learning effect, J. Oper. Res. Soc., 61, 172-177, (2010) · Zbl 1193.90115 [23] Huang, X.; Wang, J.-B.; Wang, L.-Y.; Gao, W.-J.; Wang, X.-R., Single machine scheduling with time-dependent deterioration and exponential learning effect, Comput. Indust. Eng., 58, 58-63, (2010) [24] 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 [25] Wang, J.-B.; Sun, L.-H.; Sun, L.-Y., Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect, Appl. Math. Model., 34, 2813-2819, (2010) · Zbl 1201.90088 [26] Wang, J.-B.; Li, J.-X., Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects, Appl. Math. Model., 35, 1388-1395, (2011) · Zbl 1211.90091 [27] Wang, J.-B.; Wang, M.-Z., Single machine multiple common due dates scheduling with learning effects, Comput. Math. Appl., 60, 2998-3002, (2010) · Zbl 1207.90059 [28] 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 [29] 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 [30] Wang, J.-B.; Wang, M.-Z., Worst-case analysis for flow shop scheduling problems with an exponential learning effect, J. Oper. Res. Soc., 63, 130-137, (2012) [31] Huang, X.; Wang, M.-Z.; Wang, J.-B., Single machine group scheduling with both learning effects and deteriorating jobs, Comput. Indust. Eng., 60, 750-754, (2011) [32] Lee, W. C., Scheduling with general position-based learning curves, Info. Sci., 181, 5515-5522, (2011) · Zbl 1239.90051 [33] Lee, W. C., A note on single-machine scheduling with general learning effect and past-sequence-dependent setup time, Comput. Math. Appl., 62, 2095-2100, (2011) · Zbl 1231.90203 [34] Lai, P. J.; Lee, W. C., Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects, Omega Int. J. Manage. Sci., 39, 467-471, (2011) [35] Yin, N.; Wang, X.-Y., Single machine scheduling with controllable processing times and learning effect, Int. J. Adv. Manufactur. Technol., 54, 743-748, (2011) [36] Wang, J.-B.; Wang, J.-J., Single-machine scheduling jobs with exponential learning functions, Comput. Indust. Eng., 60, 755-759, (2011) [37] Wang, J.-B.; Wang, C., Single-machine due-window assignment problem with learning effect and deteriorating jobs, Appl. Math. Model., 35, 4017-4022, (2011) · Zbl 1221.90050 [38] Wang, J.-B.; Wang, M.-Z.; Ji, P., Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs, Int. J. Syst. Sci., 43, 861-868, (2012) · Zbl 1305.90206 [39] Wang, J.-B.; Wu, Y.-B.; Ji, P., A revision of some single-machine and m-machine flowshop scheduling problems with learning considerations, Info. Sci., 190, 227-232, (2012) · Zbl 1259.90041 [40] Wang, J.-B.; Wang, M.-Z., Minimizing makespan in three-machine flow shops with deteriorating jobs, Comput. Oper. Res., 40, 547-557, (2013) · Zbl 1349.90410 [41] J.-B. Wang, C.-J. Hsu, D.-L. Yang. Single machine scheduling problems with effects of exponential learning and general deterioration, Appl. Math. Model. doi: http://dx.doi.org/10.1016/j.apm.2012.05.022. [42] X.-R. Wang, J.-J. Wang, Single-machine scheduling with convex resource dependent processing times and deteriorating jobs, Appl. Math. Model. doi: http://dx.doi.org/10.1016/j.apm.2012.05.025. · Zbl 1349.90416 [43] J.-B. Wang, X.-Y. Wang, L.-H. Sun, L.-Y. Sun, Scheduling jobs with truncated exponential learning functions, Optimiz. Lett. doi: http://dx.doi.org/10.1007/s11590-011-0433-9. · Zbl 1311.90055 [44] X.-Y. Wang, J.-J. Wang, Scheduling problems with past-sequence-dependent setup times and general effects of deterioration and learning, Appl. Math. Model. doi: http://dx.doi.org/10.1016/j.apm.2012.09.044. · Zbl 1426.90144 [45] Koulamas, C.; Kyparisis, G. J., Single-machine scheduling problems with past-sequence-dependent delivery times, Int. J. Produc. Econ., 126, 264-266, (2010) [46] Yang, S.-J.; Hsu, C.-J.; Chang, T.-R.; Yang, D.-L., Single-machine scheduling with past-sequence-dependent delivery times and learning effect, J. Chin. Inst. Indust. Eng., 28, 247-255, (2011) [47] Yang, S.-J.; Yang, D.-L., Single-machine scheduling problems with past-sequence-dependent delivery times and position-dependent processing times, J. Oper. Res. Soc., (2012) [48] Pinedo, M., Scheduling: theory, algorithms, and systems, (2002), Prentice-Hall Upper Saddle River, NJ · Zbl 1145.90394 [49] 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 [50] 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.