Notes on “Some single-machine scheduling problems with general position-dependent and time-dependent learning effects”. (English) Zbl 1231.90223
Summary: This paper provides a continuation of the idea presented by Y. Yin, D. Xu and X. Huang [Inf. Sci. 181, No. 11, 2209–2217 (2011; Zbl 1231.90223)]. For each of the following three objectives, total weighted completion time, maximum lateness and discounted total weighted completion time, this paper presents an approximation algorithm which is based on the optimal algorithm for the corresponding single-machine scheduling problem and analyzes its worst-case bound. It shows that the single-machine scheduling problems under the proposed model can be solved in polynomial time if the objective is to minimize the total lateness or minimize the sum of earliness penalties. It also shows that the problems of minimizing the total tardiness, discounted total weighted completion time and total weighted earliness penalty are polynomially solvable under some agreeable conditions on the problem parameters.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Citations:
Zbl 1231.90223References:
| [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., Single-machine scheduling with learning considerations, European Journal of Operational Research, 115, 173-178 (1999) · Zbl 0946.90025 |
| [3] | 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 |
| [4] | Chang, S.; Schneeberger, H., Single machine scheduling to minimize weighted earliness subject to no tardy jobs, European Journal of Operational Research, 34, 221-230 (1988) · Zbl 0648.90036 |
| [5] | Cheng, T. C.E.; Wang, G., Single machine scheduling with learning effect considerations, Annals of Operations Research, 98, 273-290 (2000) · Zbl 0967.68019 |
| [6] | 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, Information Sciences, 178, 2476-2487 (2008) · Zbl 1172.90397 |
| [7] | Cheng, T. C.E.; Lai, P.-J.; Wu, C.-C.; Lee, W.-C., Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations, Information Sciences, 179, 3127-3135 (2009) · Zbl 1170.90387 |
| [8] | Gawiejnowicz, S., Time-Dependent Scheduling (2008), Springer: Springer Berlin-New York · Zbl 1155.90004 |
| [9] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and heuristic in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 |
| [10] | Koulamas, C.; Kyparisis, G. J., Single-machine and two-machine flowshop scheduling with general learning functions, European Journal of Operational Research, 178, 402-407 (2007) · Zbl 1107.90018 |
| [11] | Kuo, W.-H.; Yang, D.-L., Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect, European Journal of Operational Research, 174, 1184-1190 (2006) · Zbl 1103.90341 |
| [12] | Lee, W.-C.; Wu, C.-C.; Sung, H.-J., A bi-criterion single-machine scheduling problem with learning considerations, Acta Informatica, 40, 303-315 (2004) · Zbl 1137.90500 |
| [13] | Liu, J.; Sun, S.; He, L., Some single machine scheduling problems with learning effect under consistent condition, OR Transactions, 7, 3, 21-28 (2003) |
| [14] | Kise, H.; Ibaraki, T.; Mine, H., Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times, Journal of the Operational Research Society of Japan, 22, 205-224 (1979) · Zbl 0427.90049 |
| [15] | Mosheiov, G., Scheduling problems with a learning effect, European Journal of Operational Research, 132, 687-692 (2001) · Zbl 1017.90051 |
| [16] | Park, S.-J.; Cho, K.-H., Real-time preemptive scheduling of sporadic tasks based on supervisory control of discrete event systems, Information Sciences, 178, 3393-3401 (2008) · Zbl 1142.90409 |
| [17] | Pinedo, M., Scheduling: Theory. Scheduling: Theory, Algorithms and Systems (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1145.90393 |
| [18] | Smith, W. E., Various optimizers for single-stage production, Naval Research Logistics Quarterly, 3, 59-66 (1956) |
| [19] | Tavakkoli-Moghaddam, R.; Rahimi-Vahed, A.; Mirzaei, A. H., A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness, Information Sciences, 177, 5072-5090 (2007) · Zbl 1121.90340 |
| [20] | 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) |
| [21] | Wang, J.-B.; Xia, Z.-Q., Flow-shop scheduling with a learning effect, Journal of the Operational Research Society, 56, 1325-1330 (2005) · Zbl 1082.90041 |
| [22] | Wu, C.-C.; Lee, W.-C., Single-machine scheduling problems with a learning effect, Applied Mathematical Modeling, 32, 1191-1197 (2008) · Zbl 1172.90415 |
| [23] | Xu, Z.; Sun, L.; Gong, J., Worst-case analysis for flow shop scheduling with a learning effect, International Journal of Production Economics, 113, 748-753 (2008) |
| [24] | Xu, D.; Cheng, Z.; Yin, Y.; Li, H., Makespan minimization for two parallel machines scheduling with a periodic availability constraint, Computers and Operations Research, 36, 1809-1812 (2009) · Zbl 1179.90166 |
| [25] | Xu, D.; Sun, K.; Li, H., Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan, Computers and Operations Research, 35, 1344-1349 (2008) · Zbl 1171.90411 |
| [26] | Xu, D.; Yin, Y.; Li, H., Scheduling jobs under increasing linear machine maintenance time, Journal of Scheduling, 13, 443-449 (2010) · Zbl 1231.90222 |
| [27] | Xu, D.; Yin, Y.; Li, H., A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan”, European Journal of Operational Research, 197, 825-827 (2009) · Zbl 1159.68359 |
| [28] | Yin, Y.; Xu, D.; Sun, K.; Li, H., Some scheduling problems with general position-dependent and time-dependent learning effects, Information Sciences, 179, 2416-2425 (2009) · Zbl 1166.90342 |
| [29] | Yin, Y.; Xu, D.; Wang, J., Some single-machine scheduling problems with past-sequence-dependent setup times and a general learning effect, The International Journal of Advanced Manufacturing Technology, 48, 1123-1132 (2010) |
| [30] | Yin, Y.; Xu, D.; Wang, J., Single-machine scheduling with a general sum-of-actual-processing-times-based and job-position-based learning effect, Applied Mathematical Modelling, 34, 3623-3630 (2010) · Zbl 1201.90093 |
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.
