Scheduling with non-decreasing deterioration jobs and variable maintenance activities on a single machine

ABSTRACT

There is a situation found in many manufacturing systems, such as steel rolling mills, fire fighting or single-server cycle-queues, where a job that is processed later consumes more time than that same job when processed earlier. The research finds that machine maintenance can improve the worsening of processing conditions. After maintenance activity, the machine will be restored. The maintenance duration is a positive and non-decreasing differentiable convex function of the total processing times of the jobs between maintenance activities. Motivated by this observation, the makespan and the total completion time minimization problems in the scheduling of jobs with non-decreasing rates of job processing time on a single machine are considered in this article. It is shown that both the makespan and the total completion time minimization problems are NP-hard in the strong sense when the number of maintenance activities is arbitrary, while the makespan minimization problem is NP-hard in the ordinary sense when the number of maintenance activities is fixed. If the deterioration rates of the jobs are identical and the maintenance duration is a linear function of the total processing times of the jobs between maintenance activities, then this article shows that the group balance principle is satisfied for the makespan minimization problem. Furthermore, two polynomial-time algorithms are presented for solving the makespan problem and the total completion time problem under identical deterioration rates, respectively.

KEYWORDS:

• Scheduling
• single-machine
• variable maintenance activities
• deterioration effect

Disclosure statement

No potential conflict of interest was reported by the authors.

Funding

This work was supported in part by the National Natural Science Foundation of China [numbers 11401065, 71371120, 61302180], the China Postdoctoral Science Foundation funded project [numbers 2013M540698, 2014T70854], the Foundation of Chongqing Education Commission [number KJ130606] and the Chongqing Municipal Science and Technology Commission of Natural Science Fund Projects [number cstc2014jcyjA00003]. This article was also supported in part by the Ministry of Science and Technology (MOST) of Taiwan [grant numbers NSC 102-2221-E-035-070-MY3 and MOST 103-2410-H-035-022-MY2].