×

Single-machine scheduling and slack due-date assignment with aging effect and deteriorating maintenance. (English) Zbl 1261.90020

Summary: We consider single-machine scheduling and slack due-date assignment problems simultaneously with the position-dependent aging effect and deteriorating maintenance. In order to counteract the aging effect on the machine, we assume that at most one maintenance is allowed throughout the planning horizon and the maintenance can be performed immediately after the processing of any job is completed. The maintenance duration is dependent on its starting time. The objective is to find jointly the optimal common slack time, the optimal maintenance position, and the optimal schedule such that the sum of the total earliness, the total tardiness, and the common slack time costs is minimized. We propose polynomial time algorithms for all the problems studied.

MSC:

90B35 Deterministic scheduling theory in operations research
90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adamopoulos G.I., Pappis C.P.: Single machine scheduling with flow allowances. J. Oper. Res. Soc. 47, 1280–1285 (1996) · Zbl 0863.90079
[2] Bard J.F., Venkatraman K., Feo T.A.: Single machine scheduling with flow time and earliness penalties. J. Glob. Optim. 3, 289–309 (1993) · Zbl 0801.90058 · doi:10.1007/BF01096772
[3] 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
[4] 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
[5] Browne S., Yechiali U.: Scheduling deteriorating jobs on a single processor. Oper. Res. 38, 495–498 (1990) · Zbl 0703.90051 · doi:10.1287/opre.38.3.495
[6] Brucker P.: Scheduling Algorithms. Springer, Berlin (2001) · Zbl 1051.90011
[7] Capar I., Eksioglu B.: Supply chain performance measurement. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization, Part 19, pp. 3884–3889. Springer, Berlin (2009)
[8] Cheng T.C.E., Shakhlevich N.V.: Single machine scheduling of unit-time jobs with controllable release dates. J. Glob. Optim. 27, 293–311 (2003) · Zbl 1033.90038 · doi:10.1023/A:1024826720369
[9] Cheng T.C.E., Oguz C., Qi X.D.: Due-date assignment and single machine scheduling with compressible processing times. Int. J. Prod. Econ. 43, 29–35 (1996) · doi:10.1016/0925-5273(95)00194-8
[10] Cheng T.C.E., Kang L., Ng C.T.: Single machine due-date scheduling of jobs with decreasing start-time dependent processing times. Int. Trans. Oper. Res. 12, 355–366 (2005) · Zbl 1131.90355 · doi:10.1111/j.1475-3995.2005.501_1.x
[11] Dondeti V.R., Mohanty B.B.: Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs. Eur. J. Oper. Res. 105, 509–524 (1998) · Zbl 0955.90029 · doi:10.1016/S0377-2217(97)00070-2
[12] Eksioglu B.: Global supply chain models. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization, Part 7, pp. 1434–1437. Springer, Berlin (2009)
[13] Eksioglu S.D.: Inventory management in supply chains. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization, Part 9, pp. 1766–1770. Springer, Berlin (2009)
[14] Gawiejnowicz S.: A note on scheduling on a single processor with speed dependent on a number of executed jobs. Inf. Process. Lett. 56, 297–300 (1996) · Zbl 0875.68080 · doi:10.1016/0020-0190(96)00021-X
[15] Gawiejnowicz S.: Scheduling deteriorating jobs subject to job or machine availability constraints. Eur. J. Oper. Res. 180, 472–478 (2007) · Zbl 1114.90034 · doi:10.1016/j.ejor.2006.04.021
[16] Gawiejnowicz S.: Time-dependent Scheduling. Springer, Berlin (2008) · Zbl 1155.90004
[17] Gawiejnowicz S., Kononov A.: Complexity and approximability of scheduling resumable proportionally deteriorating jobs. Eur. J. Oper. Res. 200, 305–308 (2010) · Zbl 1183.90170 · doi:10.1016/j.ejor.2008.12.014
[18] Geunes J., Chang B.: Operations research models for supply chain management and design. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization, Part 15, pp. 2704–2715. Springer, Berlin (2009)
[19] Giacomo L.D.: Mathematical programming methods in supply chain management. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization, Part 13, pp. 1959–1967. Springer, Berlin (2009)
[20] Gordon, V.S., Proth, J.M., Strusevich, V.A.: Scheduling with due date assignment. In: Leung, J. Y.-T. (eds.) Handbook of Scheduling: Algorithms, Models and Performance Analysis, pp. 21-1–21-22. CRC Press, Boca Raton (2004) · Zbl 1203.90065
[21] Gordon V.S., Tarasevich A.A.: A note: common due date assignment for a single machine scheduling with the rate-modifying activity. Comput. Oper. Res. 36, 325–328 (2009) · Zbl 1163.90488 · doi:10.1016/j.cor.2007.10.008
[22] Graham R.L., Lawler E.L., Lenstra J.K., RinnooyKan A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Disc. Math. 5, 287–326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[23] Gupta J.N.D., Gupta S.K.: Single facility scheduling with nonlinear processing times. Comput. Ind. Eng. 14, 387–393 (1988) · doi:10.1016/0360-8352(88)90041-1
[24] Hardy G.H., Littlewood J.E., Polya G.: Inequalities. Cambridge University Press, London (1967)
[25] Hsu C.-J., Low C., Su C.-T.: Single-machine scheduling problem with an availability constraint under simple linear deterioration. J. Chin. Inst. Ind. Eng. 27, 188–189 (2010)
[26] Janiak A., Rudek R.: Scheduling problems with position dependent job processing times. In: Janiak, A. (eds) Scheduling in Computer and Manufacturing Systems, pp. 26–38. Warszawa, Poland (2006)
[27] Janiak A., Rudek R.: Experience based approach to scheduling problems with the learning effect. IEEE Trans. Syst. Man Cybern. Part A 39, 344–357 (2009) · doi:10.1109/TSMCA.2008.2010757
[28] Kuo W.-H., Yang D.-L.: Minimizing the makespan in a single machine scheduling problem with the cyclic process of an aging effect. J. Oper. Res. Soc. 59, 416–420 (2008) · Zbl 1145.90387 · doi:10.1057/palgrave.jors.2602363
[29] Kuo W.-H., Yang D.-L.: A note on due-date assignment and single-machine scheduling with deteriorating jobs. J. Oper. Res. Soc. 59, 857–859 (2008) · Zbl 1153.90427 · doi:10.1057/palgrave.jors.2602396
[30] Lodree E.J. Jr, Geiger C.D.: A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration. Eur. J. Oper. Res. 201, 644–648 (2010) · Zbl 1192.90076 · doi:10.1016/j.ejor.2009.03.027
[31] Low C., Hsu C.-J., Su C.-T.: Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration. Comput. Math. Appl. 56, 257–265 (2008) · Zbl 1145.90389 · doi:10.1016/j.camwa.2007.12.006
[32] Ma Y., Chu C., Zuo C.: A survey of scheduling with deterministic machine availability constraints. Comput. Ind. Eng. 58, 199–211 (2010) · doi:10.1016/j.cie.2009.04.014
[33] 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
[34] Mosheiov G., Oron D.: Due-date assignment and maintenance activity scheduling problem. Math. Comput. Model. 44, 1053–1057 (2006) · Zbl 1161.90397 · doi:10.1016/j.mcm.2006.03.008
[35] Mosheiov G., Sidney J. B.: Scheduling a deteriorating maintenance activity on a single machine. J. Oper. Res. Soc. 61, 882–887 (2010) · Zbl 1193.90106 · doi:10.1057/jors.2009.5
[36] Papadimitriou C.H., Steiglitz K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, New Jersey (1982) · Zbl 0503.90060
[37] Panwalkar S.S., Smith M.L., Seidmann A.: Common due date assignment to minimize total penalty for the one machine scheduling problem. Oper. Res. 30, 391–399 (1982) · Zbl 0481.90042 · doi:10.1287/opre.30.2.391
[38] Shabtay D., Steiner G.: The single-machine earliness–tardiness scheduling problem with due date assignment and resource-dependent processing times. Ann. Oper. Res. 159, 25–40 (2008) · Zbl 1151.90432 · doi:10.1007/s10479-007-0269-y
[39] Szwarc W., Mukhopadhyay S.K.: Earliness and tardiness single machine scheduling with proportional weights. J. Glob. Optim. 9, 227–238 (1996) · Zbl 0863.90093 · doi:10.1007/BF00121673
[40] Wang J.-B.: Single machine scheduling with common due date and controllable processing times. Appl. Math. Comput. 174, 1245–1254 (2006) · Zbl 1111.90048 · doi:10.1016/j.amc.2005.05.046
[41] Wang J.-B.: Single machine common flow allowance scheduling with controllable. J. Appl. Math. Comput. 21, 249–257 (2006) · Zbl 1105.90029 · doi:10.1007/BF02896403
[42] 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 · doi:10.1016/j.apm.2009.04.020
[43] Wang X.-Y., Wang M.-Z.: Single machine common flow allowance scheduling with a rate-modifying activity. Comput. Ind. Eng. 59, 898–902 (2010) · doi:10.1016/j.cie.2010.08.020
[44] Wu C.-C., Lee W.-C.: Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine. Inf. Process. Lett. 87, 89–93 (2003) · Zbl 1161.68367 · doi:10.1016/S0020-0190(03)00262-X
[45] Yang S.-J., Hsu C.-J., Yang D.-L.: Single-machine scheduling with due-date assignment and aging effect under a deteriorating maintenance activity consideration. Int. J. Inform. Manage. Sci. 21, 177–195 (2010) · Zbl 1230.90105
[46] Yang S.-J., Yang D.-L.: Single-machine scheduling problems with aging/deteriorating effect under an optional maintenance activity consideration. INFOR 48, 171–179 (2010)
[47] Yang S.-J., Yang D.-L.: Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities. Omega 38, 528–533 (2010) · doi:10.1016/j.omega.2010.01.003
[48] Yang S.-J., Yang D.-L.: Minimizing total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities. Comput. Math. Appl. 60, 2161–2169 (2010) · Zbl 1205.90141 · doi:10.1016/j.camwa.2010.08.003
[49] Zhao C.-L., Tang H.-Y.: Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan. Appl. Math. Model. 34, 837–841 (2010) · Zbl 1185.90106 · doi:10.1016/j.apm.2009.07.002
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.