zbMATH — the first resource for mathematics

Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration. (English) Zbl 1145.90389
Summary: This article considers a single machine scheduling problem with an availability constraint under simple linear deterioration. The non-preemptive case is taken into account as well. The objective is to minimize the makespan in the system. The addressed problem is first described as a 0-1 integer programming model, and is then solved optimally. Subsequently, we prove that the addressed problem belongs to NP-hard. Thus, some heuristic algorithms based on the bin packing concepts are provided for solving the addressed problem. Computational results show that the proposed algorithm H3 performs well. In addition, a good strategy that sets the maintenance to start epoch when half the jobs have been already processed is suggested as well.

90B35 Deterministic scheduling theory in operations research
90B25 Reliability, availability, maintenance, inspection in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90C10 Integer programming
Full Text: DOI
[1] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Operations research, 38, 495-498, (1990) · Zbl 0703.90051
[2] Kunnathur, A.S.; Gupta, S.K., Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, European journal of operations research, 47, 56-64, (1990) · Zbl 0717.90034
[3] Mosheiov, G., Scheduling jobs with step-deterioration: minimizing makespan on single and multi-machine, Computers and industrial engineering, 28, 869-879, (1995)
[4] Mosheiov, G., Scheduling deteriorating jobs under simple linear deterioration, Computers and operations research, 21, 653-659, (1994) · Zbl 0810.90074
[5] Cheng, T.C.E.; Ding, Q.; Lin, B.M.T., A concise survey of scheduling with time-dependent processing times, European journal of operations research, 152, 1-13, (2004) · Zbl 1030.90023
[6] Wu, C.C.; Lee, W.C., Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine, Information processing letters, 87, 89-93, (2003) · Zbl 1161.68367
[7] Ji, M.; He, Y.; Cheng, T.C.E., Scheduling linear deteriorating jobs with an availability constraint on a single machine, Theoretical computer science, 362, 115-126, (2006) · Zbl 1100.68009
[8] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[9] Johnson, D.S., The NP-complete columns: an ongoing guide, Journal of algorithms, 4, 393-405, (1981) · Zbl 0494.68047
[10] Mosheiov, G., Multi-machine scheduling with linear deterioration, Infor, 36, 4, 205-214, (1998)
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.