Competition in market place prompts the studies on operations management to improve customer service. One important objective of operations management in practice is to finish jobs as close as possible to their due-dates. Usually a time period, namely due-window of a job, is assigned in the supply contract so that a job completed within the time period will not be penalized. The due-window assignment methods include common due-window, slack due-window (also called common flow allowance) and others. Some relevant references are   etc. A polynomial-time solution was introduced to obtain the optimal schedule and the optimal due-window size with the minimum total cost in  .
In classical scheduling theory, job processing times are considered as constants. However, a steadily growing interest on solving scheduling problems with changeable job processing times has been witnessed in the last decade. Kang et al.  showed that the problem of minimizing makespan on m identical parallel machines with time-dependent processing times is NP-hard, and presented a fully polynomial-time approximation scheme for the problem. The single machine common due-window assignment problem considering deteriorating jobs and learning effect was studied by  . A polynomial-time algorithm was presented to give a solution to minimize the total cost consisting of the penalties of earliness, tardiness, window location and window size. Yin et al.  investigated the single machine scheduling problems with sum-of-logarithm-processing-times based deterioration.
Machine scheduling for a rate-modifying activity was first studied by  . In this paper, the maintenance activity considered is different from the rate-modifying activity. At most one maintenance activity is scheduled and the scheduler can decide when to start the maintenance activity. After the maintenance activity the machine reverts to its initial conditions including machine deterioration. The research on the similar assumption can be found in  and  .
The combinations of the above-mentioned settings have been considered in the following recent literatures. Based on the common due-window assignment method, Zhao and Tang  studied the scheduling problem with a rate-modifying activity and time-dependent deteriorating jobs, and Cheng et al.  investigated the problem with a maintenance activity and time-dependent deteriorating jobs.  and  studied the problem to minimize the total cost consisting of earliness, tardiness, due-window starting time, due-window size, and resource consumption with a common due-window and a deteriorating rate-modifying activity. In this paper, the problem of slack due-window assignment and single-machine scheduling considering a maintenance activity and time-dependent deteriorating jobs is presented. To our best knowledge, this problem has not been studied in literatures.
The rest of this paper is organized as follows. In Section 2, a description of the problem is given. In Section 3, some important lemmas and properties are presented. In Section 4, a polynomial-time solution for the problem is given. A numerical example is presented to demonstrate the polynomial-time solution in Section 5. The research is concluded and future study is foreseen in the last section.
2. Model Formulation
A single machine processes n jobs denoted by . Here any job is ready for processing at time zero. No preemption is allowed. Let denote the normal processing time of job and let non-negative t denote the starting time of job . A common deteriorating factor b is specified for all the jobs. The actual processing time of job is determined by according to a linear time-dependent deteriorating model.
The due window of job is specified by a pair of non-negative real numbers such that . For a given schedule , denotes the completion time of job , is the earliness value of job , is the tardiness value of job , and is the due-window size of job . For the slack due-window method, the due window starting time and the due window completion time for job are defined as
respectively. Note that is the processing time of job . Since and are two job-independent constants, which satisfy , the window size is also a constant for all the jobs. Let .
Furthermore, the following assumptions have been made for this problem. First, the machine reverts to its initial conditions including machine deterioration after the maintenance activity. Second, there is at most one maintenance activity throughout the schedule. Note that it is unnecessary to allocate a maintenance activity after the final job. Third, a similar linear time-dependent deteriorating model is adopted to calculate maintenance duration. The duration is determined by basic maintenance time (a positive constant), maintenance factor and the starting time t of maintenance activity such as .
The objective function consists of four cost components, i.e. 1) earliness , 2) tardiness , 3) the starting time of the due-window , and 4) the due-window size D. Let , , and represent the earliness, tardiness, due-window starting time and due-window size costs per unit time respectively. The general objective is to determine the optimal and , the optimal position of the maintenance activity, and the optimal schedule to minimize the total cost function
The problem under study is denoted as
where SLK and ma in the second field denote the slack due-window method and maintenance activity, respectively.
3. Properties of an Optimal Solution
In this section some properties for an optimal schedule are obtained.
Lemma 1. If for a given job order , then .
Proof: We have
Similar to the proof of Lemma 1, we have
Lemma 2. If for a given job order , then .
Consider a job sequence . Assume that and . Then the total cost Z is a linear function of and , and thus an optimum is obtained either at or and either at or .
Therefore we obtain the following result, whose proof is similar to the one in  .
Lemma 3. 1) For any given job sequence, the optimal values of and are equal to the completion times of the k’th and l’th jobs where .
2) An optimal schedule starts at time zero.
3) No idle time exists between consecutive jobs in an optimal schedule.
4) An optimal schedule exists in which the maintenance activity takes place right after the completion of one of the jobs.
For a number a, denotes the largest integer not more than a.
Lemma 4. and .
Proof: Shift to the left by time units, where . As a result, the overall cost Z has been changed by . Since
is optimal, it implies that , and hence .
Shift to the right by time units, where . As a result, the overall cost Z has been changed by . We obtain
, and hence . Then .
In the similar way, we can prove by using the standard perturbation method. ,
Lemma 5. Suppose that sequences and are given except in arrangement. The sum of the products of the corresponding elements is minimized if the sequences are monotonic in opposite senses.
Proof: See page 261 in  . ,
4. Optimal Solution
Let denote the actual processing time and let denote the normal processing time of the job scheduled in the rth position in a sequence. The positions of k and l can be determined based on Lemma 4. Let i be the position of the last job preceding the maintenance activity. If the position of the maintenance activity is before k (i.e., ), then the total cost is given by
If , then we have
If , then we have
It is evident that if no maintenance activity needs to schedule. Given the processing time , the actual processing time of the scheduled j'th job can be given as follows.
where , and
Combining (4), (6) and (8) and using (10), we obtain
the positional weight
Based on the above analysis and the rearrangement inequality (Lemma 5), we give the following algorithm to solve the problem
In Step 7, by Lemma 5, we arrange the job with the largest normal processing time to the position with the smallest value of , the job with the second largest normal processing time to the position with the second smallest value of , and so forth.
To this end, we obtain the following result.
Theorem 1. Algorithm 1 solves the problem in time.
Proof: The correction of Algorithm 1 is guaranteed by Lemmas 3-5. The time complexity of the inner loop from Step 3 to Step 8 is . In the outer loop from Step 2 to Step 9, position index i takes on integer values between 1 to n. Hence, the time complexity for solving the problem is .
5. Numerical Example
In this section, Algorithm 1 is illustrated by the following example.
Example 1. The normal processing times of jobs are , , , , , , , and . The overall cost consists of four specific costs for unit earliness , unit tardiness , unit due-window size and unit due-window starting time . Set the common deteriorating factor , the deteriorating maintenance factor , and the basic maintenance time .
Solution: As shown in Step 1 in Algorithm 1, we determine and .
As shown in Table 1, all the local optimal job sequences and their total costs are presented, among which the optimal total cost is underlined. The global optimal solution for this example is illustrated as: 1) the job sequence is (7, 8, 6, 3, 5, 1, 2, 4, 9) and the corresponding job starting time and actual processing time are (0.00, 70.50, 79.50, 98.95, 125.37, 154.12, 220.30, 308.79, 402.70) and
Table 1. The corresponding local optimal job sequences and total costs with one maintenance activity at all possible positions in Example 1.
(55.00, 9.00, 19.45, 26.42, 28.74, 66.18, 88.49, 93.91, 107.61), respectively; 2) the slack window parameters are and ; 3) the maintenance activity is located right after the first job (i.e. Job 7), starting at time and ending at time ; 4) the total cost is .
We solved a single machine slack due-window assignment and scheduling problem of a deteriorating maintenance activity and linear time-dependent deteriorating jobs, and gave a polynomial-time algorithm. The running time of this algorithm does not exceed . The problem with the setting of parallel identical machines, or the problems with min-max type objective functions may be considered in the future.
This work was supported by NSFGD (2018A030313267).
 Liman, S., Panwalkar, S. and Thongmee, S. (1998) Common Due Window Size and Location Determination in a Single Machine Scheduling Problem. Journal of the Operational Research Society, 49, 1007-1010.
 Kang, L.Y., Cheng, T.C.E., Ng, C.T. and Zhao, M. (2005) Scheduling to Minimize Makespan with Time-Dependent Processing Times. Lecture Notes in Computer Science, 3827, 925-933.
 Wang, J.-B. and Wang, C. (2011) Single-Machine Due-Window Assignment Problem with Learning Effect and Deteriorating Jobs. Applied Mathematical Modelling, 35, 4017-4022.
 Yin, N., Kang, L.Y., Ji, P. and Wang, J.B. (2014) Single Machine Scheduling with Sum-of-Logarithm-Processing-Times Based Deterioration. Information Sciences, 274, 303-309.
 Zhao, C.-L. and Tang, H.-Y. (2010) Single Machine Scheduling with General Job-Dependent Aging Effect and Maintenance Activities to Minimize Makespan. Applied Mathematical Modelling, 34, 837-841.
 Cheng, T.C.E., Yang, S.-J. and Yang, D.-L. (2012) Common Due-Window Assignment and Scheduling of Linear Time-Dependent Deteriorating Jobs and a Deteriorating Maintenance Activity. In-ternational Journal of Production Economics, 135, 154-161.
 Zhao, C.-L. and Tang, H.-Y. (2012) A Note to Due-Window Assignment and Single Machine Scheduling with Deteriorating Jobs and a Rate-Modifying Activity. Computers & Operations Research, 39, 1300-1303.
 Ji, M., Ge, J., Chen, K. and Cheng, T.E. (2013) Single-Machine Due-Window Assignment and Scheduling with Resource Allocation, Aging Effect, and a Deteriorating Rate-Modifying Activity. Computers & Industrial Engineering, 66, 952-961.
 Cheng, B. and Cheng, L. (2014) Note on Single-Machine Due-Window Assignment and Scheduling with Re-source Allocation, Aging Effect, and a Deteriorating Rate- Modifying Activity? Com-puters & Industrial Engineering, 78, 320-322.