Scheduling jobs with truncated exponential learning functions. (English) Zbl 1311.90055
Summary: In this paper we consider the single machine scheduling problem with truncated exponential learning functions. By the truncated exponential learning functions, we mean that the actual job processing time is a function which depends not only on the total normal processing times of the jobs already processed but also on a control parameter. The use of the truncated function is to model the phenomenon that the learning of a human activity is limited. We show that even with the introduction of the proposed model to job processing times, several single machine problems remain polynomially solvable. For the following three objective functions, the total weighted completion time, the discounted total weighted completion time, the maximum lateness, we present heuristic algorithms according to the corresponding problems without truncated exponential learning functions. We also analyse the worst-case bound of our heuristic algorithms.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Badiru A.B.: Computational survey of univariate and multivariate learning curve models. IEEE Trans. Eng. Manag. 39, 176–188 (1992) · doi:10.1109/17.141275 |
| [2] | Biskup D.: Single-machine scheduling with learning considerations. Eur. J. Oper. Res. 115, 173–178 (1999) · Zbl 0946.90025 · doi:10.1016/S0377-2217(98)00246-X |
| [3] | Biskup D.: A state-of-the-art review on scheduling with learning effects. Eur. J. Oper. Res. 188, 315–329 (2008) · Zbl 1129.90022 · doi:10.1016/j.ejor.2007.05.040 |
| [4] | 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. Industr. Eng. 60, 534–541 (2011) · doi:10.1016/j.cie.2010.12.008 |
| [5] | 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. Inform. Sci. 179, 3127–3135 (2009) · Zbl 1170.90387 · doi:10.1016/j.ins.2009.05.002 |
| [6] | Cheng T.C.E., Wang G.: Single machine scheduling with learning effect considerations. Ann. Oper. Res. 98, 273–290 (2000) · Zbl 0967.68019 · doi:10.1023/A:1019216726076 |
| [7] | Cheng T.C.E., Wu C.-C., Lee W.-C.: Some scheduling problems with deteriorating jobs and learning effects. Comput. Industr. Eng. 54, 972–982 (2008) · doi:10.1016/j.cie.2007.11.006 |
| [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. Inform. Sci. 178, 2476–2487 (2008) · Zbl 1172.90397 · doi:10.1016/j.ins.2008.02.002 |
| [9] | Floudas C.A., Pardalos P.M.: Encyclopedia of Optimization, 2nd edn. Springer, Berlin (2009) · Zbl 1156.90001 |
| [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. Ann. Discret. Math. 5, 287–326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [11] | Hadda H.: A ( $${\(\backslash\)frac{4}{3}}$$ )-approximation algorithm for a special case of the two machine flow shop problem with several availability constraints. Optim. Lett. 3, 583–592 (2009) · Zbl 1176.90218 · doi:10.1007/s11590-009-0137-6 |
| [12] | Lai P.J., Lee W.C.: Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects. Omega Int. J. Manag. Sci. 39, 467–471 (2011) · doi:10.1016/j.omega.2010.10.002 |
| [13] | Lee W.C.: Scheduling with general position-based learning curves. Inform. Sci. 181, 5515–5522 (2011) · Zbl 1239.90051 · doi:10.1016/j.ins.2011.07.051 |
| [14] | Lee W.-C., Wu C.-C.: Some single-machine and m-machine flowshop scheduling problems with learning considerations. Inform. Sci. 179, 3885–3892 (2009) · Zbl 1179.90141 · doi:10.1016/j.ins.2009.07.011 |
| [15] | 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 · doi:10.1016/j.apm.2008.05.020 |
| [16] | Lee C.-Y., Yu G.: Parallel-machine scheduling under potential disruption. Optim. Lett. 2, 27–37 (2008) · Zbl 1145.90023 · doi:10.1007/s11590-006-0041-2 |
| [17] | 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 · doi:10.1057/palgrave.jors.2602480 |
| [18] | Pardalos P.M., Resende M.G.C.: Handbook of Applied Optimization. Oxford Univ Press, Oxford (2002) · Zbl 0996.90001 |
| [19] | Pardalos P.M.: Complexity in Numerical Optimization. World Scientific, Singapore (1993) · Zbl 0872.90002 |
| [20] | Setamaa-Karkkainen A., Miettinen K., Vuori J.: Heuristic for a new multiobjective scheduling problem. Optim. Lett. 1, 213–225 (2007) · Zbl 1152.90467 · doi:10.1007/s11590-006-0020-7 |
| [21] | Pinedo M.: Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, Upper Saddle River (2002) · Zbl 1145.90394 |
| [22] | Smith W.E.: Various optimizers for single state production. Naval Res. Log. Quart. 3, 59–66 (1956) · doi:10.1002/nav.3800030106 |
| [23] | Townsend W.: The single machine problem with quadratic penalty function of completion times: a branch-and-bound solution. Manag. Sci. 24, 530–534 (1978) · Zbl 0371.90065 · doi:10.1287/mnsc.24.5.530 |
| [24] | 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 · doi:10.1016/j.apm.2010.09.017 |
| [25] | Wang J.-B., Sun L.-H., Sun L.-Y.: Single machine scheduling with a learning effect and discounted costs. Int. J. Adv. Manufact. Technol. 49, 1141–1149 (2010) · doi:10.1007/s00170-009-2477-x |
| [26] | Wang J.-B., Wang M.-Z.: Single machine multiple common due dates scheduling with general job-dependent learning curves. Comput. Math. Appl. 60, 2998–3002 (2010) · Zbl 1207.90059 · doi:10.1016/j.camwa.2010.09.061 |
| [27] | 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 · doi:10.1016/j.mcm.2010.08.020 |
| [28] | 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 · doi:10.1007/s10479-011-0923-2 |
| [29] | Wang, J.-B., Wang, M.-Z.: Single-machine scheduling with nonlinear deterioration. Optim. Lett. doi: 10.1007/s11590-010-0253-3 · Zbl 1259.90040 |
| [30] | Wang, J.-B., Ji, P., Cheng, T.C.E., Wang, D.: Minimizing makespan in a two-machine flow shop with effects of deterioration and learning. Optim. Lett. doi: 10.1007/s11590-011-0334-y · Zbl 1259.90039 |
| [31] | Wang J.-J., Wang J.-B., Wang X.-P.: Scheduling problems with exponential learning functions. Int. J. Innovat. Comput. Inform. Control 6, 3265–3274 (2010) |
| [32] | 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 · doi:10.1016/j.camwa.2008.09.025 |
| [33] | Wright T.P.: Factors affecting the cost of airplanes. J. Aeronaut. Sci. 3, 122–128 (1936) · doi:10.2514/8.155 |
| [34] | Wu C.-C., Lee W.-C.: Single-machine and flowshop scheduling with a general learning effect model. Comput. Industr. Eng. 56, 1553–1558 (2009) · doi:10.1016/j.cie.2008.10.002 |
| [35] | Wu C.-C., Yin Y., Cheng S.-R.: Some single-machine scheduling problems with a truncation learning effect. Comput. Industr. Eng. 60, 790–795 (2011) · doi:10.1016/j.cie.2011.01.016 |
| [36] | Yang D.-L., Kuo W.-H.: Single-machine scheduling with both deterioration and learning effects. Ann. Oper. Res. 172, 315–327 (2009) · Zbl 1181.90131 · doi:10.1007/s10479-009-0615-3 |
| [37] | Yang D.-L., Kuo W.-H.: Some scheduling problems with deteriorating jobs and learning effects. Comput. Industr. Eng. 58, 25–28 (2010) · doi:10.1016/j.cie.2009.06.016 |
| [38] | Yin Y., Xu D., Sun K., Li H.: Some scheduling problems with general position-dependent and time-dependent learning effects. Inform. Sci. 179, 2416–2425 (2009) · Zbl 1166.90342 · doi:10.1016/j.ins.2009.02.015 |
| [39] | Zhao C.-L., Tang H.-Y.: A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints. Optim. Lett. 5, 183–190 (2011) · Zbl 1213.90127 · doi:10.1007/s11590-010-0202-1 |
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.
