Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties.

*(English)*Zbl 1230.90103Summary: We consider identical parallel machines scheduling problems with a deteriorating maintenance activity. In this model, each machine has a deteriorating maintenance activity, that is, delaying the maintenance increases the time required to perform it. We need to make a decision on when to schedule the rate-modifying activities and the sequence of jobs to minimize some objective function. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remain polynomially solvable under the proposed model.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

PDF
BibTeX
XML
Cite

\textit{J.-B. Wang} and \textit{C.-M. Wei}, Appl. Math. Comput. 217, No. 20, 8093--8099 (2011; Zbl 1230.90103)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Lee, C.-Y.; Leon, V.J., Machine scheduling with a rate-modifying activity, European journal of operational research, 128, 119-128, (2001) · Zbl 0983.90020 |

[2] | Graves, G.H.; Lee, C.-Y., Scheduling maintenance and semiresumable jobs on a single machine, Naval research logistics, 46, 845-863, (1999) · Zbl 0931.90015 |

[3] | Qi, X.; Chen, T.; Tu, F., Scheduling the maintenance on a single machines, Journal of operational research society, 50, 1071-1078, (1999) · Zbl 1054.90550 |

[4] | Lee, C.-Y.; Chen, Z.-L., Scheduling jobs and maintenance activities on parallel machine, Naval research logistics, 47, 145-165, (2000) · Zbl 0973.90034 |

[5] | Lee, C.-Y.; Lin, C.-S., Single-machine scheduling with maintenance and repair rate-modifying activity, European journal of operational research, 135, 493-513, (2001) · Zbl 0989.90036 |

[6] | L.O. Whitaker, Integrated production and maintenance activities, MS Thesis, Department of Industrial Engineering, Texas A&M University, College Station, TX, 1996. |

[7] | Mosheiov, G.; Oron, D., Due-date assignment and maintenance activity scheduling problem, Mathematical and computer modelling, 44, 1053-1057, (2006) · Zbl 1161.90397 |

[8] | Mosheiov, G.; Sidney, J.B., New results on sequencing with rate modification, Infor, 41, 155-163, (2004) |

[9] | Gordon, V.S.; Tarasevich, A.A., A note: common due date assignment for a single machine scheduling with the rate-modifying activity, Computers and operations research, 36, 325-328, (2009) · Zbl 1163.90488 |

[10] | Zhao, C.-L.; Tang, H.-Y.; Cheng, C.-D., Two-parallel machines scheduling with rate-modifying activities to minimize total completion time, European journal of operational research, 198, 354-357, (2009) · Zbl 1163.90518 |

[11] | Sun, K.; Li, H., Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines, International journal of production economics, 124, 151-158, (2010) |

[12] | Ji, M.; Cheng, T.C.E., Scheduling with job-dependent learning effects and multiple rate-modifying activities, Information processing letters, 110, 460-463, (2010) · Zbl 1229.90061 |

[13] | Kubzin, M.A.; Strusevich, V.A., Planning machine maintenance in two-machine shop scheduling, Operations research, 54, 789-800, (2006) · Zbl 1167.90669 |

[14] | Mosheiov, G.; Sidney, J.B., Scheduling a deteriorating maintenance activity on a single machine, Journal of operational research society, 61, 882-887, (2010) · Zbl 1193.90106 |

[15] | Wang, J.-J.; Wang, J.-B.; Liu, F., Scheduling a deteriorating maintenance activity on a single machine, Journal of operational research society, (2010) · Zbl 1193.90106 |

[16] | Yang, S.-J.; Yang, D.-L.; Cheng, T.C.E., Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance, Computers and operations research, 37, 1510-1514, (2010) · Zbl 1183.90203 |

[17] | 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) |

[18] | Yang, S.-J.; Yang, D.-L., Minimizing total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities, Computers and mathematics with applications, 60, 2161-2169, (2010) · Zbl 1205.90141 |

[19] | Cheng, T.C.E.; Yang, S.-J.; Yang, D.-L., Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity, International journal of production economics, (2010) |

[20] | Cheng, T.C.E.; Hsu, C.-J.; Yang, D.-L., Unrelated parallel-machine scheduling with deteriorating maintenance activities, Computers and industrial engineering, (2010) |

[21] | Yang, S.-J., Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration, Applied mathematics and computation, 217, 3321-3329, (2011) · Zbl 1202.90149 |

[22] | Merten, A.G.; Muller, M.E., Variance minimization in single machine sequencing problems, Management science, 18, 518-528, (1972) · Zbl 0254.90040 |

[23] | Schrage, L., Minimizing the time-in-system variance for a finite jobset, Management science, 21, 540-543, (1975) · Zbl 0302.90021 |

[24] | Eilon, S.; Chowdhury, I.E., Minimizing waiting time variance in the single machine problem, Management science, 23, 567-575, (1977) · Zbl 0362.90051 |

[25] | Vani, V.; Raghavachari, M., Deterministic and random single machine sequencing with variance minimization, Operations research, 35, 111-120, (1987) · Zbl 0616.90027 |

[26] | Wang, J.-B.; Xia, Z.-Q., Single machine scheduling problems with controllable processing times and total absolute differences penalties, European journal of operational research, 177, 638-645, (2007) · Zbl 1109.90045 |

[27] | Mor, B.; Mosheiov, G., Total absolute deviation of job completion times on uniform and unrelated machines, Computers and operations research, 38, 660-665, (2011) · Zbl 1201.90083 |

[28] | Kanet, J.J., Minimizing variation of flow time in single machine systems, Management science, 27, 1453-1459, (1981) · Zbl 0473.90048 |

[29] | Bagchi, U.B., Simultaneous minimization of Mean and variation of flow-time and waiting time in single machine systems, Operations research, 37, 118-125, (1989) · Zbl 0661.90046 |

[30] | Cheng, T.C.E.; Ding, Q.; Lin, B.M.T., A concise survey of scheduling with time-dependent processing times, European journal of operational research, 152, 1-13, (2004) · Zbl 1030.90023 |

[31] | Gawiejnowicz, S., Time-dependent scheduling, (2008), Springer Berlin, ISBN:978-3-540-69445-8 |

[32] | Wang, J.-B., Single machine scheduling with a time-dependent learning effect and deteriorating jobs, Journal of the operational research society, 60, 583-586, (2009) · Zbl 1163.90515 |

[33] | Yang, S.-H.; Wang, J.-B., Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration, Applied mathematics and computation, 217, 4819-4826, (2011) · Zbl 1230.90104 |

[34] | Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of discrete mathematics, 5, 287-326, (1979) · Zbl 0411.90044 |

[35] | Mosheiov G, G., Parallel machine scheduling with a learning effect, Journal of the operational research society, 52, 1165-1169, (2001) · Zbl 1178.90159 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.