Scheduling identical jobs on uniform parallel machines under position-based learning effects. (English) Zbl 1390.90320
Summary: This research considers the problem of scheduling identical jobs on uniform parallel machines for the individual minimization of several different performance measures under position-based learning effects. The performance measures include total weighted completion time, total tardiness, total weighted tardiness, and maximum lateness. We formulate these problems as assignment problems with nonlinear or linear objectives. The \(n\) earliest completion times can be used in non-decreasing order to reduce the number of variables significantly and to find optimal solutions efficiently. Our computational results show that it is more efficient to formulate these problems as assignment problems with nonlinear objectives and a few variables and constraints than to formulate them as linear programming models with many variables and constraints.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
References:
| [1] | 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 |
| [2] | 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 |
| [3] | Pinedo M.L.: Scheduling: Theory Algorithms and Systems. Prentice Hall, New York (2012) · Zbl 1239.90002 · doi:10.1007/978-1-4614-2361-4 |
| [4] | Baptiste, P.; Brucker, P.: Scheduling equal processing time jobs. In: Leung, J.Y-T. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, 14.1-14.37, Chapman & Hall/CRC, New York (2004) · Zbl 1211.90084 |
| [5] | Dessouky M.I., Lageweg B.J., Lenstra J.K., van de Velde S.L.: Scheduling identical jobs on uniform parallel machines. Stat. Neerl. 44, 115-123 (1990) · Zbl 0716.90053 · doi:10.1111/j.1467-9574.1990.tb01276.x |
| [6] | Blazewicz J., Dror M., Weglarz J.: Mathematical programming formulations for machine scheduling: a survey. Eur. J. Oper. Res. 51, 283-300 (1991) · Zbl 0734.90040 · doi:10.1016/0377-2217(91)90304-E |
| [7] | Gawiejnowicz S.: A note on scheduling on a single processor with speed dependent on a number of executed jobs. Inf. Process. Lett. 57, 297-300 (1996) · Zbl 0875.68080 · doi:10.1016/0020-0190(96)00021-X |
| [8] | Mosheiov G.: Scheduling problems with a learning effect. Eur. J. Oper. Res. 132, 687-693 (2001) · Zbl 1017.90051 · doi:10.1016/S0377-2217(00)00175-2 |
| [9] | Lu Y.Y., Wei C.M., Wang J.B.: Several scheduling problems with general learning effects. Appl. Math. Model. 36, 5650-5656 (2012) · Zbl 1254.90073 · doi:10.1016/j.apm.2012.01.022 |
| [10] | Wang J.B., Wang J.J.: Single-machine scheduling with precedence constraints and position-dependent processing times. Appl. Math. Model. 37, 649-658 (2013) · Zbl 1351.90103 · doi:10.1016/j.apm.2012.02.055 |
| [11] | Wang J.B, Wu Y.B., Ji P.: A revision of some single-machine and m-machine flowshop scheduling problems with learning considerations. Inf. Sci. 190, 227-232 (2012) · Zbl 1259.90041 · doi:10.1016/j.ins.2011.10.003 |
| [12] | 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 |
| [13] | Sun, L.H., Cui, K., Chen, J.H., Wang, J., He, X.C.: Some results of the worst-case analysis for flow shop scheduling with a learning effect. Ann. Oper. Res. (2013). doi:10.1007/s10479-013-1368-6 · Zbl 1286.90067 |
| [14] | Behnamian J., Zandieh M.: Earliness and tardiness minimizing on a realistic hybrid flowshop scheduling with learning effect by advanced metaheuristic. Arab. J. Sci. Eng. 38, 1229-1242 (2013) · doi:10.1007/s13369-012-0347-6 |
| [15] | Mosheiov G.: Parallel machine scheduling with a learning effect. J. Oper. Res. Soc. 52, 1165-1169 (2001) · Zbl 1178.90159 · doi:10.1057/palgrave.jors.2601215 |
| [16] | Mosheiov G., Sidney J.B.: Scheduling with general job-dependent learning curves. Eur. J. Oper. Res. 147, 665-670 (2003) · Zbl 1037.90529 · doi:10.1016/S0377-2217(02)00358-2 |
| [17] | Zhao C., Zhang Q., Tang H.: Machine scheduling problems with a Learning effect. Dyn. Contin. Discret. Impuls. Syst. Ser. A Math. Anal. 11, 741-750 (2004) · Zbl 1142.90413 |
| [18] | Eren T.: A note on minimizing maximum lateness in an m-machine scheduling problem with a learning effect. Appl. Math. Comput. 209, 186-190 (2009) · Zbl 1156.90360 · doi:10.1016/j.amc.2008.12.003 |
| [19] | Toksari M.D., Güner E.: Minimizing the earliness/tardiness costs on parallel machine with learning effects and deteriorating jobs: a mixed nonlinear integer programming approach. Int. J. Adv. Manuf. Technol. 38, 801-808 (2008) · doi:10.1007/s00170-007-1128-3 |
| [20] | Toksari M.D., Güner E.: Parallel machine earliness/tardiness scheduling problem under the effects of position based learning and linear/nonlinear deterioration. Comput. Oper. Res. 36, 2394-2417 (2009) · Zbl 1179.90158 · doi:10.1016/j.cor.2008.09.012 |
| [21] | Okołowski D., Gawiejnowicz S.: Exact and heuristic algorithms for parallel-machine scheduling with DeJong’s learning effect. Comput. Ind. Eng. 59, 272-279 (2010) · doi:10.1016/j.cie.2010.04.008 |
| [22] | Hsu C.J., Kuo W.H., Yang D.L.: Unrelated parallel machine scheduling with past-sequence-dependent setup time and learning effects. Appl. Math. Model. 35, 1492-1496 (2011) · Zbl 1211.90084 · doi:10.1016/j.apm.2010.09.026 |
| [23] | Huang, X., Wang, M.-Z., Ji, P.: Parallel machines scheduling with deteriorating and learning effects. Optim. Lett. (2012). doi:10.1007/s11590-012-0490-8 · Zbl 1288.90029 |
| [24] | Lee W.C., Chuang M.C., Yeh W.C.: Uniform parallel-machine scheduling to minimize makespan with position-based learning curves. Comput. Ind. Eng. 63, 813-818 (2012) · doi:10.1016/j.cie.2012.05.003 |
| [25] | Lin Y.K.: Fast LP models and algorithms for identical jobs on uniform parallel machines. Appl. Math. Model. 37(5), 3436-3448 (2013) · Zbl 1351.90099 · doi:10.1016/j.apm.2012.07.023 |
| [26] | Potts C.N., Van Wassenhove L.N.: A decomposition algorithm for the single machine total tardiness problem. Oper. Res. Lett. 1, 177-181 (1982) · Zbl 0508.90045 · doi:10.1016/0167-6377(82)90035-9 |
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.
