zbMATH — the first resource for mathematics

Scheduling a maintenance activity on parallel identical machines. (English) Zbl 1158.90350
Summary: We study a problem of scheduling a maintenance activity on parallel identical machines, under the assumption that all the machines must be maintained simultaneously. One example for this setting is a situation where the entire system must be stopped for maintenance because of a required electricity shut-down. The objective is minimum flow-time. The problem is shown to be NP-hard, and moreover impossible to approximate unless \(P = NP\). We introduce a pseudo-polynomial dynamic programming algorithm, and show how to convert it into a bicriteria FPTAS for this problem. We also present an efficient heuristic and a lower bound. Our numerical tests indicate that the heuristic provides in most cases very close-to-optimal schedules.

90B35 Deterministic scheduling theory in operations research
90C39 Dynamic programming
Full Text: DOI
[1] Anily, The scheduling of maintenance service, Discrete Appl Math 82 pp 27– (1998) · Zbl 0897.90119
[2] Anily, Scheduling maintenance services to three machine, Ann Oper Res 86 pp 375– (1999) · Zbl 0921.90087
[3] Bellman, Applied dynamic programming (1962)
[4] Conway, Theory of scheduling (1967) · Zbl 1058.90500
[5] Grigoriev, Modeling and solving periodic maintenance problem, Eur J Oper Res 172 pp 783– (2006) · Zbl 1111.90028
[6] Kubzin, Planning machine maintenance in two-machine shop scheduling, Oper Res 54 pp 789– (2006) · Zbl 1167.90669
[7] Lee, Handbook of scheduling: Algorithms, models and performance analysis (2004)
[8] Lee, Scheduling jobs and maintenance activities on parallel machines, Naval Res Logist 47 pp 145– (2000) · Zbl 0973.90034
[9] Lee, Machine scheduling with a rate modifying activity, Eur J Oper Res 129 pp 119– (2001) · Zbl 0983.90020
[10] Mosheiov, Due-date assignment and maintenance activity scheduling problem, Math Comput Model 44 pp 1053– (2006) · Zbl 1161.90397
[11] Pinedo, Scheduling: Theory, algorithms and systems (1995)
[12] Schmidt, Scheduling with limited machine availability, Eur J Oper Res 121 pp 1– (2000) · Zbl 0959.90023
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.