This paper explores a single-machine scheduling with aging effects and the problem regarding optional maintenance activity assignment. The jobs’ processing time is assumed to follow a power position-dependent aging model. The optional maintenance activity refers to the situation in which the maintenance activity can be scheduled immediately after processing of any job has been completed except for the last job and the duration of maintenance activity can be of any value from zero to a fixed time interval. A recovery function is proposed to reflect the efficiency of the machine or worker which is improved. The objective of this study is to decide whether and when to implement the maintenance activity into the job sequence, how long the duration of maintenance activity is, and how to schedule so as to minimize the makespan. Once the duration of maintenance activity is known, we introduce an efficient solution for this problem. In addition, when the maintenance activity is completely performed, we showed that the optimal policy is to schedule the maintenance activity in the middle of the task sequence and optimally solved it by lower order algorithm. Finally, we extend the problem to the case of multiple maintenance activities which are completely performed. Hence, the problem is regarded as polynomial time solvable.

Scheduling problems with aging (deterioration or fatigue) effects have been extensively studied over two decades in various machine environments and performance measures. The processing time of a job is an increasing function of its position to be processed in its starting time. The increasing model reflects many realistic situations such as steel production [

We introduced some papers which have only related scheduling jobs with aging (deterioration) effect and availability constraint simultaneously as follows. Wu and Lee [

Production scheduling and maintenance planning are the most common and significant problems faced by the manufacturing industry. In the real production settings, machines are usually not continuously available. For instance, in the manufacturing industry, a machine may not be available in the scheduling period due to a preventive maintenance, tool change, or others for assuring that the product retains its high quality. The stop time interval will affect the objectives of production system. There are numerous papers on this theme. For details on this stream of research, the reader may refer to the comprehensive surveys by Schmidt [

The scheduling problem explored in this paper was motivated by the manufacturing of the metal processing industry [

The problem rendered in this paper can be formally described as follows.There are

For the characteristics of the aging effects, assume that there is at most one maintenance activity which is allowed throughout the planning horizon. It can be scheduled immediately after the processing of any job has been completed except for the last job. The basic duration of the maintenance activity is

According to the above equation in above, one has the following scenarios.

If

If

If

By using the general notation for scheduling problems, the problem is denoted by a triplet

Since the length of maintenance activity (break time) affects the extent of recovery and the efficiency of the operations management, in order to achieve the objective, production manager needs to decide an optimal policy depending on whether to implement the maintenance activity, when to implement the maintenance activity, and how long for performing the maintenance activity. In this section, we will analyze the problem accordingly. First, a useful lemma which will be applied to solve the problem is given as follows.

Let there be two sequences of numbers

See page 261 in Hardy et al. [

For any job sequence, if the OMA is scheduled at position

For the

For the specific schedule

Clearly, the OMA should be scheduled to the position

Once the duration of maintenance activity (

Consider the following.

The time complexity of Step 1 is

For the

Next, one derives the optimal policy for assigning an adequate length of

If the

Clearly, (

By Theorem

If the length of the maintenance activity is

Let

Applying to the weight-matching approach, the following theorem holds immediately.

Problem

Assume

For the convenience, we assume that there are 10 independent jobs to be processed on a single-machine scheduling, with the aging rate

Finally, one explores the case of

Let

Consider the following.

Comparing at most (

Assume that there are 30 independent jobs to be processed on a single-machine scheduling, with the aging rate

This paper examined a recovery function for the position-dependent aging with an optional maintenance activity. Once the duration of maintenance activity is known, one showed that the proposed problems are polynomial time solvable. Furthermore, if the maintenance activity is completely performed, one concluded that the optimal policy is to schedule the maintenance activity in the middle of the task sequence and it may optimally be solved by lower order algorithm. Next, one investigated the case of multiple maintenance activities which are completely performed in the planning horizon. Result showed that the problem is also polynomial time solvable. To sum up, by applying the optimal solution function, the decision maker may easily find the optimal times of maintenance activities.

It is worthwhile for future research to consider the problem with other regular performance measures, due-window related topics, or multimachine settings. Extensions the recovery function to the job-dependent and/or time-dependent processing time models are worth investigating, not only in the context of our problem but for all traditional objective functions.

The author is grateful to the lead guest editor and two anonymous referees for their helpful comments on an earlier version of this paper. This research was supported by the National Science Council of China, under Grant no. NSC 102-2221-E-252-007.