×

Parallel-machine scheduling with potential disruption and positional-dependent processing times. (English) Zbl 1364.90378

Summary: In this paper, we address the scheduling problem with positional-dependent processing times in a disruptive environment, in which there is a possibility that some of the machines become unavailable for a certain period of time with a certain probability due to a disruption at a particular time. By positional-dependent processing times, we mean that the actual processing time of a job depends on its processing position on a machine. Since some machines may be unavailable for a certain period of time, both non-resumable and resumable cases are considered. The objective is to minimize the expected total completion time. For various cases, we provide the complexity results and present efficient pseudo-polynomial time algorithms for the corresponding problems.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Biskup, Single-machine scheduling with learning considerations,, European Journal of Operational Research, 115, 173 (1999) · Zbl 0946.90025 · doi:10.1016/S0377-2217(98)00246-X
[2] G. H. Hardy, <em>Inequalities</em>,, Cambridge: Cambridge University Press (1934) · JFM 60.0169.01
[3] R. L. Graham, Optimization and approximation in deterministic machine scheduling: A survey,, Annals of Discrete Mathematics, 5, 287 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[4] J.-Y. Kung, Some cheduling problems on a single machine with general job effects of position-dependent learning and start-time-dependent deterioration,, Asia-Pacific Journal of Operational Research, 32 (2015) · Zbl 1319.90033 · doi:10.1142/S0217595915500025
[5] C.-Y. Lee, Machine scheduling with an availability constraint. Special Issue on “Optimization on Scheduling Application”,, Journal of global optimination, 9, 395 (1996) · Zbl 0870.90071 · doi:10.1007/BF00121681
[6] C.-Y. Lee, Current trends in deterministic scheduling,, Annals of Operations Research, 70, 1 (1997) · Zbl 0890.90102 · doi:10.1023/A:1018909801944
[7] C.-Y. Lee, Single machine flow-time scheduling with scheduled maintenance,, Acta Informatica, 29, 375 (1992) · Zbl 0738.68043 · doi:10.1007/BF01178778
[8] C.-Y. Lee, Single machine scheduling under potential disruption,, Operations Research Letters, 35, 541 (2007) · Zbl 1278.90163 · doi:10.1016/j.orl.2006.08.005
[9] C.-Y. Lee, Parallel-machine scheduling under potential disruption,, Optimization Letters, 2, 27 (2008) · Zbl 1145.90023 · doi:10.1007/s11590-006-0041-2
[10] A. Levin, Scheduling a maintenance activity on parallel identical machines,, Naval Research Logistics, 56, 33 (2009) · Zbl 1158.90350 · doi:10.1002/nav.20324
[11] Y. Ma, A survey of scheduling with deterministic machine availability constraints,, Computers & Industrial Engineering, 58, 199 (2010) · doi:10.1016/j.cie.2009.04.014
[12] G. Mosheiov, A note on scheduling deteriorating jobs,, Mathematical and Computer Modelling, 41, 883 (2005) · Zbl 1082.90038 · doi:10.1016/j.mcm.2004.09.004
[13] J.-B. Wang, Single-machine scheduling problems with the effects of learning and deterioration,, Omega, 35, 397 (2007) · doi:10.1016/j.omega.2005.07.008
[14] J.-B. Wang, Flow-shop scheduling with a learning effect,, Journal of the Operational Research Society, 56, 1325 (2005) · Zbl 1082.90041 · doi:10.1057/palgrave.jors.2601856
[15] X.-Y. Wang, Scheduling deteriorating jobs with a learning effect on unrelated parallel machines,, Applied Mathematical Modelling, 38, 5231 (2014) · Zbl 1428.90072 · doi:10.1016/j.apm.2014.04.002
[16] E. Sanlaville, Machine scheduling with availability constraints,, Acta Informatica, 35, 795 (1998) · Zbl 0917.68018 · doi:10.1007/s002360050143
[17] G. Schmidt, Scheduling with limited machine availability,, European Journal of Operational Research, 121, 1 (2000) · Zbl 0959.90023 · doi:10.1016/S0377-2217(98)00367-1
[18] D.-L. Yang, A single-machine scheduling problem with learning effects in intermittent batch production,, Computers & Industrial Engineering, 57, 762 (2009) · doi:10.1016/j.cie.2009.02.003
[19] Y. Yin, Single machine scheduling with job position-dependent learning and time-dependent deterioration,, IEEE Transactions on Systems, 42, 192 (2012) · doi:10.1109/TSMCA.2011.2147305
[20] Y. Yin, Single-machine scheduling with time-dependent and position-dependent deteriorating jobs,, International Journal of Computer Integrated Manufacturing, 28, 781 (2015) · doi:10.1080/0951192X.2014.900872
[21] Y. Yin, Due date assignment and single-machine scheduling with generalized positional deteriorating jobs and deteriorating multi-maintenance activities,, International Journal of Production Research, 52, 2311 (2014)
[22] Y. Yin, Notes on “some single-machine scheduling problems with general position-dependent and time-dependent learning effects”,, Information Sciences, 181, 2209 (2011) · Zbl 1231.90223 · doi:10.1016/j.ins.2011.01.018
[23] Y. Yin, Some scheduling problems with general position-dependent and time-dependent learning effects,, Information Sciences, 179, 2416 (2009) · Zbl 1166.90342 · doi:10.1016/j.ins.2009.02.015
[24] C. Zhao, Single-machine scheduling and due date assignment with rejection and position-dependent processing times,, Journal of Industrial and Management Optimization, 10, 691 (2014) · Zbl 1292.90130 · doi:10.3934/jimo.2014.10.691
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.