Single Machine Slack Due-Window Assignment and Scheduling of Linear Time-Dependent Deteriorating Jobs and a Deteriorating Maintenance Activity

Abstract

In this paper, we consider the slack due-window assignment model and study a single machine scheduling problem of linear time-dependent deteriorating jobs and a deteriorating maintenance activity. The objective is to find the job schedule having an assigned maintenance activity and due-windows with the minimum total cost consisting of costs of earliness, tardiness, window location and window size. A polynomial-time algorithm is presented in this paper with time complexity for n jobs.

Share and Cite:

Cheng, B. and Cheng, L. (2018) Single Machine Slack Due-Window Assignment and Scheduling of Linear Time-Dependent Deteriorating Jobs and a Deteriorating Maintenance Activity. Open Access Library Journal, 5, 1-9. doi: 10.4236/oalib.1104907.

1. Introduction

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 [1] [2] etc. A polynomial-time solution was introduced to obtain the optimal schedule and the optimal due-window size with the minimum total cost in [3] .

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. [4] 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 [5] . 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. [6] 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 [7] . 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 [8] and [9] .

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 [10] studied the scheduling problem with a rate-modifying activity and time-dependent deteriorating jobs, and Cheng et al. [9] investigated the problem with a maintenance activity and time-dependent deteriorating jobs. [11] and [12] 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 J 1 , J 2 , , J n . Here any job is ready for processing at time zero. No preemption is allowed. Let a j denote the normal processing time of job J j and let non-negative t denote the starting time of job J j . A common deteriorating factor b is specified for all the jobs. The actual processing time p j of job J j is determined by p j = a j + b t according to a linear time-dependent deteriorating model.

The due window of job J j is specified by a pair of non-negative real numbers [ d j ( 1 ) , d j ( 2 ) ] such that d j ( 1 ) d j ( 2 ) . For a given schedule π , C j = C j ( π ) denotes the completion time of job J j , E j = max { 0 , d j ( 1 ) C j } is the earliness value of job J j , T j = max { 0 , C j d j ( 2 ) } is the tardiness value of job J j , and D j = d j ( 2 ) d j ( 1 ) is the due-window size of job J j . For the slack due-window method, the due window starting time d j ( 1 ) and the due window completion time d j ( 2 ) for job J j are defined as

d j ( 1 ) = p j + q ( 1 ) , (1)

and

d j ( 2 ) = p j + q ( 2 ) , (2)

respectively. Note that p j is the processing time of job J j . Since q ( 1 ) and q ( 2 ) are two job-independent constants, which satisfy q ( 2 ) > q ( 1 ) , the window size D j = q ( 2 ) q ( 1 ) is also a constant for all the jobs. Let D = D j .

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 T m a is determined by basic maintenance time μ (a positive constant), maintenance factor σ and the starting time t of maintenance activity such as T m a = μ + σ t .

The objective function consists of four cost components, i.e. 1) earliness E j , 2) tardiness T j , 3) the starting time of the due-window d j ( 1 ) , and 4) the due-window size D. Let α > 0 , β > 0 , γ > 0 and δ > 0 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 q ( 1 ) and q ( 2 ) , the optimal position of the maintenance activity, and the optimal schedule to minimize the total cost function

Z = j = 1 n ( α E j + β T j + γ d j ( 1 ) + δ D ) . (3)

The problem under study is denoted as

1 | S L K , p j = a j + b t , m a | j = 1 n ( α E j + β T j + γ d j ( 1 ) + δ D )

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 C j d j ( 2 ) for a given job order π = ( J 1 , J 2 , , J n ) , then C j + 1 d j + 1 ( 2 ) .

Proof: We have

C j + 1 C j + p j + 1 d j ( 2 ) + p j + 1 = q ( 2 ) + p j + p j + 1 = d j + 1 ( 2 ) + p j d j + 1 ( 2 ) .

,

Similar to the proof of Lemma 1, we have

Lemma 2. If C j d j ( 1 ) for a given job order π = ( J 1 , J 2 , , J n ) , then C j 1 d j 1 ( 1 ) .

Consider a job sequence π = ( J 1 , J 2 , , J n ) . Assume that C s q ( 1 ) C s + 1 and C t q ( 2 ) C t + 1 . Then the total cost Z is a linear function of q ( 1 ) and q ( 2 ) , and thus an optimum is obtained either at q ( 1 ) = C s or q ( 1 ) = C s + 1 and either at q ( 2 ) = C t or q ( 2 ) = C t + 1 .

Therefore we obtain the following result, whose proof is similar to the one in [13] .

Lemma 3. 1) For any given job sequence, the optimal values of q ( 1 ) and q ( 2 ) are equal to the completion times of the k’th and l’th jobs where k l .

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, a denotes the largest integer not more than a.

Lemma 4. k = n ( δ γ ) α and l = n ( β δ ) β .

Proof: Shift q ( 1 ) to the left by Δ time units, where 0 < Δ < p k . As a result, the overall cost Z has been changed by ( δ n n γ α k ) Δ . Since

q ( 1 ) = p 1 + p 2 + + p k is optimal, it implies that ( δ n n γ α k ) Δ 0 , and hence k n ( δ γ ) α .

Shift q ( 1 ) to the right by Δ time units, where 0 < Δ < p k + 1 . As a result, the overall cost Z has been changed by ( α ( k + 1 ) + n γ δ n ) Δ . We obtain

( α ( k + 1 ) + n γ δ n ) Δ 0 , and hence k n ( δ γ ) α 1 . Then k = n ( δ γ ) α .

In the similar way, we can prove l = n ( β δ ) β by using the standard perturbation method. ,

Lemma 5. Suppose that sequences x 1 , x 2 , , x n and y 1 , y 2 , , y n are given except in arrangement. The sum of the products of the corresponding elements j = 1 n x j y j is minimized if the sequences are monotonic in opposite senses.

Proof: See page 261 in [14] . ,

4. Optimal Solution

Let p [ r ] denote the actual processing time and let a [ r ] 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., i < k ), then the total cost is given by

Z = j = 1 n ( α E j + β T j + γ d j ( 1 ) + δ D ) = α j = 1 k ( p [ j ] + q ( 1 ) C [ j ] ) + β j = l + 1 n ( C [ j ] p [ j ] q ( 2 ) ) + γ j = 1 n ( q ( 1 ) + p [ j ] ) + n δ ( q ( 2 ) q ( 1 ) ) = α j = 1 k j p [ j ] + α i ( μ + σ j = 1 i p [ j ] ) + β j = l + 1 n ( n j ) p [ j ] + γ ( n ( μ + σ j = 1 i p [ j ] ) + ( n + 1 ) j = 1 k p [ j ] + j = k + 1 n p [ j ] ) + n δ j = k + 1 l p [ j ] = n μ γ + α i μ + j = 1 n ω j p [ j ] , (4)

where

ω j = ( α j + α i σ + γ n σ + ( n + 1 ) γ 1 j i α j + ( n + 1 ) γ i < j k γ + n δ k < j l β ( n j ) + γ l < j n (5)

If k i < l , then we have

Z = α j = 1 k j p [ j ] + β j = l + 1 n ( n j ) p [ j ] + γ ( ( n + 1 ) j = 1 k p [ j ] + j = k + 1 n p [ j ] ) + n δ ( μ + σ j = 1 i p [ j ] ) + n δ j = k + 1 l p [ j ] = n δ μ + j = 1 n ω j p [ j ] , (6)

where

ω j = ( α j + γ ( n + 1 ) + n δ σ 1 j k γ + n δ σ + n δ k < j i γ + n δ i < j l β ( n j ) + γ l < j n (7)

If l i n , then we have

Z = α j = 1 k j p [ j ] + β ( j = l + 1 n ( n j ) p [ j ] + ( n i ) ( μ + σ j = 1 i p [ j ] ) ) + γ ( ( n + 1 ) j = 1 k p [ j ] + j = k + 1 n p [ j ] ) + n δ j = k + 1 l p [ j ] = ( n i ) β μ + j = 1 n ω j p [ j ] , (8)

where

ω j = ( α j + β ( n i ) σ + γ ( n + 1 ) 1 j k β ( n i ) σ + γ + n δ k < j l β ( n j ) + β ( n i ) σ + γ l < j i β ( n j ) + γ i < j n (9)

It is evident that if i = n no maintenance activity needs to schedule. Given the processing time a [ j ] , the actual processing time p [ j ] of the scheduled j'th job can be given as follows.

p [ j ] = a [ j ] + b t = 1 m 1 ( 1 + b ) t 1 a [ j t ] , (10)

where 1 j n , and

m = ( j if j i j i if j > i (11)

Combining (4), (6) and (8) and using (10), we obtain

Z = M + j = 1 n ω j p [ j ] = M + j = 1 n W j a [ j ] , (12)

where

M = ( n μ γ + α i μ i < k n δ μ k i < l ( n i ) β μ l i n (13)

the positional weight

W j = ω j + b t = j + 1 m ω t ( 1 + b ) t j 1 , (14)

and

m = ( i if 1 j i n if i < j n (15)

Based on the above analysis and the rearrangement inequality (Lemma 5), we give the following algorithm to solve the problem

1 | S L K , p j = a j + b t , m a | j = 1 n ( α E j + β T j + γ d j ( 1 ) + δ D )

In Step 7, by Lemma 5, we arrange the job with the largest normal processing time to the position with the smallest value of W j , the job with the second largest normal processing time to the position with the second smallest value of W j , and so forth.

To this end, we obtain the following result.

Theorem 1. Algorithm 1 solves the problem 1 | S L K , p j = a j + b t , m a | j = 1 n ( α E j + β T j + γ d j ( 1 ) + δ D ) in O ( n 2 l o g n ) 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 O ( n l o g n ) . 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 1 | S L K , p j = a j + b t , m a | j = 1 n ( α E j + β T j + γ d j ( 1 ) + δ D ) problem is O ( n 2 l o g n ) .

5. Numerical Example

In this section, Algorithm 1 is illustrated by the following example.

Example 1. The normal processing times of n = 9 jobs are a 1 = 62 , a 2 = 81 , a 3 = 25 , a 4 = 82 , a 5 = 26 , a 6 = 19 , a 7 = 55 , a 8 = 9 and a 9 = 91 . The overall cost consists of four specific costs for unit earliness α = 4 , unit tardiness β = 15 , unit due-window size δ = 6 and unit due-window starting time γ = 5 . Set the common deteriorating factor b = 0.05 , the deteriorating maintenance factor σ = 0.1 , and the basic maintenance time μ = 10 .

Solution: As shown in Step 1 in Algorithm 1, we determine k = n ( δ γ ) α = 2 and l = n ( β δ ) β = 5 .

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 q ( 1 ) = 79.50 and q ( 2 ) = 154.12 ; 3) the maintenance activity is located right after the first job (i.e. Job 7), starting at time t = 55.00 and ending at time t = 70.50 ; 4) the total cost is Z = 17476.37 .

6. Conclusion

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 O ( n 2 l o g n ) . The problem with the setting of parallel identical machines, or the problems with min-max type objective functions may be considered in the future.

Fund

This work was supported by NSFGD (2018A030313267).

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] Cheng, T.C.E. (1988) Optimal Common Due-Date with Limited Completion Time Deviation. Computers & Operations Research, 15, 91-96.
https://doi.org/10.1016/0305-0548(88)90001-9
[2] 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.
https://doi.org/10.1057/palgrave.jors.2600601
[3] Mosheiov, G. and Sarig, A. (2008) A Multi-Criteria Scheduling with Due-Window Assignment Problem. Mathematical and Computer Modelling, 48, 898-907.
https://doi.org/10.1016/j.mcm.2007.08.018
[4] 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.
https://doi.org/10.1007/11602613_92
[5] 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.
https://doi.org/10.1016/j.apm.2011.02.023
[6] 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.
https://doi.org/10.1016/j.ins.2014.03.004
[7] Lee, C.-Y. and Leon, V. (2001) Machine Scheduling with a Rate-Modifying Activity. European Journal of Operational Research, 128, 119-128.
https://doi.org/10.1016/S0377-2217(99)00066-1
[8] 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.
https://doi.org/10.1016/j.apm.2009.07.002
[9] 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.
https://doi.org/10.1016/j.ijpe.2010.10.005
[10] 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.
https://doi.org/10.1016/j.cor.2010.04.006
[11] 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.
https://doi.org/10.1016/j.cie.2013.08.020
[12] 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.
https://doi.org/10.1016/j.cie.2014.07.013
[13] Mosheiov, G. and Oron, D. (2010) Job-Dependent Due-Window Assignment Based on a Common Flow Allowance. Foundations of Computing and Decision Sciences, 35, 185-195.
[14] Hardy, G.H., Littlewood, J.E. and Pólya, G. (1934) Inequalities. 1em plus 0.5em minus 0.4em. Cambridge University Press.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.