Back
 JCC  Vol.6 No.1 , January 2018
Flow Shop Scheduling Problem with Convex Resource Allocation and Learning Effect
Abstract: In this paper, we consider the no-wait two-machine scheduling problem with convex resource allocation and learning effect under the condition of common due date assignment. We take the total earliness, tardiness and common due date cost as the objective function, and find the optimal common due date, the resource allocation and the schedule of jobs to make the objective function minimum under the constraint condition that the total resource is limited. The corresponding algorithm is given and proved that the problem can be solved in polynomial time.

1. Introduction

In the scheduling problem of industrial production, the processing of the job is complicated. The processing time of the job in the classic scheduling problem is a constant, but in the actual production, the actual processing time of the job is often related to the normal processing time of the job, allocation of resources, learning effects, deteriorating effects of the machine and other factors. In view of the complexity of the current scheduling problem, a large number of scholars have given their own research. In 1980, Vickson [1] first proposed that the processing time has the resources controllable problem, which broke through the classic model of the scheduling problem and brought new research directions in the scheduling field. In actual industrial production, managers often use non-renewable resources as a tool to control the processing time of the job, so as to improve the running effect of the system. The scheduling problem of resource-constrained processing time has also attracted the attention of scholars. In actual industrial production, with the improvement of worker's proficiency and the shorter machining time of the job, Biskup [2] first proposed a scheduling problem with learning effect, and gave a new model. Wang et al. [3] studied the single machine scheduling problems with learning effects and resource allocation, and obtained the optimal schedule, resource allocation and optimal algorithm. Shabaty and Kaspi [4] proposed scheduling problems with convex resource-dependent processing times, and discussed the single-machine problems with the minimization of the total weighted flow time. Since then, Leyvand et al. [5] have proposed and demonstrated a uniform approach to scheduling problems with convex resource allocation. Zhu et al. [6] studied group scheduling problem with learning effect and resource allocation on a single-machine. Wang and Wang [7] studied the single machine scheduling problem with learning effect and convex resource-dependent processing time. Liu et al. [8] studied two-machine scheduling problem with learning effect and convex resource processing time under common due date, and gave the optimal algorithm to prove that it is solvable in polynomial time. Lu et al. [9] considered the optimal due-date assignment problem with learning effect and resource-dependent processing times. Li et al. [10] studied a single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation. Yin et al. [11] studied a single machine scheduling problem with learning effects and controllable processing time. Gao et al. [12] considered two-machine no-wait flow shop scheduling problem with learning effect and convex resource allocation. Under the common due date condition, they proved the problem can be solved in polynomial time.

In this paper, we consider the two-machine no-wait flow shop scheduling problem with learning effects and convex resource allocation. Under limited resource availability, some results are given.

2. Problem Formulation

There are n independent jobs { J 1 , J 2 , ... , J n } to be processed on a two-machine flow shop setting. Each job is required to be processed on machine M 1 and then on machine M 2 , and between the two machines, the jobs are not allowed to wait, the operation O j i ( j = 1 , 2 , ... , n ; i = 1 , 2 ). The processing time of each job is give as follows:

P j i = ( p ¯ j i r a u j i ) m (1)

where P j i is the actual processing time of operation O j i , p ¯ j i is the normal processing time of operation O j i , u j i represents the amount of a non-renewable resource allocated to operation O j i , r is the actual scheduling position of the job J j , a is the learning index( a 0 ), m is a positive constant.

In this model, d is the common due date, C j is the completion time of job J j , E j = max { 0 , d C j } is the earliness of job J j , T j = max { 0 , C j d } is the tardiness of job J j . The purpose is to determine the optimal schedule π = ( J [ 1 ] , J [ 2 ] , J [ 3 ] , ... , J [ n ] ) , the optimal resource allocation strategy u [ j ] 1 * , u [ j ] 2 * , and

the common due date d of jobs under the condition i = 1 2 j = 1 n u j i G so that the following objective function is minimized:

f ( π , u , d ) = j = 1 n ( α E j + β T j + γ d ) (2)

where weights α , β , γ are given constants ( α 0 , β 0 , γ 0 ). In what follows, the problem studied will be denoted by using the extended three-field notation scheme (Graham et al. [13]).

3. Main Results

Lemma 1. (Gao et al. [12]) For any specified schedule π , there exists an optimal common due date with the property that the common due date value d coincides with the completion time of a job.

Lemma 2. (Gao et al. [12]) For the

F 2 | n o w a i t , P j i = ( p ¯ j i r a u j i ) m , i = 1 2 j = 1 n u j i G | j = 1 n ( α E j + β T j + γ d )

problem, an optimal sequence exists such that d = C [ k ] , where

k = min { max { ( β γ ) n α + β , 0 } , n } (3)

As in Gao et al. [12], for a no-wait flow shop problem with a constraint C [ j + 1 ] 1 C [ j ] 2 , we have

f ( π , u , d ) = j = 1 n ( α E j + β T j + γ d ) = α j = 1 k-1 ( d C [ j ] ) + β j = k + 1 n ( C [ j ] d ) + γ n d = α ( j = 2 k ( j 1 ) p [ j ] 1 + ( k 1 ) p [ k ] 2 j = 1 k 1 p [ j ] 2 )

+ β ( j = k + 1 n ( n j + 1 ) p [ j ] 1 ( n k ) p [ k ] 2 + j = k + 1 n p [ j ] 2 ) + γ ( n j = 1 k p [ j ] 1 + n p [ k ] 2 ) = α j = 2 k ( j 1 ) p [ j ] 1 + β j = k + 1 n ( n j + 1 ) p [ j ] 1 + γ n j = 1 k p [ j ] 1 + ( α ( k 1 ) p [ k ] 2 β ( n k ) p [ k ] 2 + γ n p [ k ] 2 ) + ( β j = k + 1 n p [ j ] 2 α j = 1 k 1 p [ j ] 2 ) = j = 1 n ω j ( p ¯ [ j ] 1 j a u [ j ] 1 ) m + j = 1 n υ j ( p ¯ [ j ] 2 j a u [ j ] 2 ) m (4)

where

ω j = { n γ , j = 1 α ( j 1 ) + γ n , j = 2 , 3 , ... , k β ( n j + 1 ) , j = k + 1 , k + 2 , ... , n (5)

and

υ j = { α , j = 1 , 2 , ... , k 1 α ( k 1 ) β ( n k ) + γ n , j = k β , j = k + 1 , k + 2 , ... , n (6)

Lemma 3. For a given sequence π = ( J [ 1 ] , J [ 2 ] , J [ 3 ] , ... , J [ n ] ) , the optimal resource allocation u * ( π ) for the problem

F 2 | n o w a i t , p j i = ( p ¯ j i r a u j i ) m , i = 1 2 j = 1 n u j i G | j = 1 n ( α E j + β T j + γ d )

is:

u [ j ] 1 * = G ( ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 j = 1 n ( ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 + j = 1 n ( υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 j = 1 , 2 , ... , n (7)

u [ j ] 2 * = G ( υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 j = 1 n ( ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 + j = 1 n ( υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 , j = 1 , 2 , ... , n (8)

Proof. Obviously under the condition i = 1 2 j = 1 n u j i = G , we can get the minimum value of the objective function.

Min f ( π , u , d ) = j = 1 n ( α E j + β T j + γ d )

S.t. i = 1 2 j = 1 n u j i G = 0 (9)

According to Lagrangian multiplier method, from (9) and (4), we have:

L ( π , u , d , λ ) = f ( π , u , d ) + λ ( i = 1 2 j = 1 n u j i G ) = j = 1 n ( α E j + β T j + γ d ) + λ ( i = 1 2 j = 1 n u j i G ) = j = 1 n ω j ( p ¯ [ j ] 1 j a u [ j ] 1 ) m + j = 1 n υ j ( p ¯ [ j ] 2 j a u [ j ] 2 ) m + λ ( j = 1 n u [ j ] 1 + j = 1 n u [ j ] 2 G ) (10)

where λ is the Lagrangian multiplier.

Since each of the objectives is a convex function, according to Lagrangian multiplier method.

Differentiating (10) with respect to u [ j ] 1 , we have

L ( π , u , d , λ ) u [ j ] 1 = λ m ω j × ( p ¯ [ j ] 1 j a ) m ( u [ j ] 1 ) m + 1 = 0 , j = 1 , 2 , ... , n (11)

then

u [ j ] 1 * = ( m ω j λ ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 , j = 1 , 2 , ... , n (12)

Differentiating (10) with respect to u [ j ] 2 , we have

L ( π , u , d , λ ) u [ j ] 2 = λ m υ j × ( p ¯ [ j ] 2 j a ) m ( u [ j ] 2 ) m + 1 = 0 , j = 1 , 2 , ... , n (13)

then

u [ j ] 2 * = ( m υ j λ ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 , j = 1 , 2 , ... , n (14)

Differentiating (10) with respect to λ , we have

L ( π , u , d , λ ) λ = j = 1 n u [ j ] 1 + j = 1 n u [ j ] 2 G = 0 (15)

Substituting (12) and (14) into (15), we have

λ 1 m + 1 = j = 1 n ( m ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 G + j = 1 n ( m υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 G (16)

From (16) and (12), we have

u [ j ] 1 * = G ( ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 j = 1 n ( ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 + j = 1 n ( υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 j = 1 , 2 , ... , n

From (16) and (14), we have

u [ j ] 2 * = G ( υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 j = 1 n ( ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 + j = 1 n ( υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 , j = 1 , 2 , ... , n

Substituting (7) and (8) into (4), under optimal resource allocation u [ j ] 1 * , u [ j ] 2 * and π = ( J [ 1 ] , J [ 2 ] , J [ 3 ] , ... , J [ n ] ) , we obtain that a new unified expression for f ( π , u , d ) = j = 1 n ( α E j + β T j + γ d ) .

f ( π , u ( π ) , d ) = j = 1 n ( α E j + β T j + γ d ) = j = 1 n ω j ( p ¯ [ j ] 1 j a u [ j ] 1 ) m + j = 1 n υ j ( p ¯ [ j ] 2 j a u [ j ] 2 ) m = j = 1 n ω j ( p ¯ [ j ] 1 j a u [ j ] 1 ) m + j = 1 n υ j ( p ¯ [ j ] 2 j a u [ j ] 2 ) m = G m ( j = 1 n ( ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 × ( j = 1 n ( ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 + j = 1 n ( υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 ) m ) + j = 1 n ( υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 × ( j = 1 n ( ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 + j = 1 n ( υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 ) m ) ) m + 1 = G m ( j = 1 n ( ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 + j = 1 n ( υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1 ) ) m + 1 (17)

In what follows, we derive the optimal schedule for

F 2 | n o w a i t , p j i = ( p ¯ j i r a u j i ) m , i = 1 2 j = 1 n u j i G | j = 1 n ( α E j + β T j + γ d )

It is clear that the minimum value of (17) is equal to minimizing

j = 1 n ( ω j ) 1 m + 1 ( p ¯ [ j ] 1 j a ) m m + 1 + j = 1 n ( υ j ) 1 m + 1 ( p ¯ [ j ] 2 j a ) m m + 1

Let us define binary variables x j r , such that x j r = 1 , if job J j ( j = 1 , 2 , ... , n ) is scheduled at position r ( r = 1 , 2 , ... , n ) , otherwise x j r = 0 . Then, the problem

F 2 | n o w a i t , p j i = ( p ¯ j i r a u j i ) m , i = 1 2 j = 1 n u j i G | j = 1 n ( α E j + β T j + γ d )

can be solved by the following linear assignment problem:

Min r = 1 n j = 1 n θ j r x j i (18)

S.t. r = 1 n x j r = 1 , j = 1 , 2 , ... , n (19)

j = 1 n x j r = 1 , r = 1 , 2 , ... , n (20)

x j r = 0 o r 1 , j = 1 , 2 , .. , n , r = 1 , 2 , ... , n (21)

where

θ j r = ( ω r ) 1 m + 1 ( p ¯ j 1 r a ) m m + 1 + ( υ r ) 1 m + 1 ( p ¯ j 2 r a ) m m + 1 (22)

ω r = { n γ , r = 1 α ( r 1 ) + γ n , r = 2 , 3 , ... , k β ( n r + 1 ) , r = k + 1 , k + 2 , ... , n (23)

and

υ r = { α , r = 1 , 2 , ... , k 1 α ( k 1 ) β ( n k ) + γ n , r = k β , r = k + 1 , k + 2 , ... , n (24)

By solving this linear assignment problem, we can get the optimal job sequence π = ( J [ 1 ] , J [ 2 ] , J [ 3 ] , ... , J [ n ] ) of the problem

F 2 | n o w a i t , p j i = ( p ¯ j i r a u j i ) m , i = 1 2 j = 1 n u j i G | j = 1 n ( α E j + β T j + γ d )

Based on the above analysis, our algorithm for

F 2 | n o w a i t , p j i = ( p ¯ j i r a u j i ) m , i = 1 2 j = 1 n u j i G | j = 1 n ( α E j + β T j + γ d )

can be described as follows.

Algorithm 1

Step 1. According to (3), calculate k = min { max { ( β γ ) n α + β , 0 } , n } .

Step 2. According to (22), calculate the θ j r .

Step 3. Solve the linear assignment problem (18)-(21) to determine the optimal job sequence π = ( J [ 1 ] , J [ 2 ] , J [ 3 ] , ... , J [ n ] ) .

Step 4. According to (7) and (8), calculate the optimal resource allocation u [ j ] 1 * , u [ j ] 2 * .

Step 5. According to (1), calculate the actual processing times p j i .

Step 6. Calculate the common due date d = C [ k ] .

Theorem 1. The problem

F 2 | n o w a i t , p j i = ( p ¯ j i r a u j i ) m , i = 1 2 j = 1 n u j i G | j = 1 n ( α E j + β T j + γ d )

can be solved in O ( n 3 ) time by Algorithm 1.

Proof. According to the lemmas 1, 2, 3 and the assignment problem (18)-(21), we can get the correctness of Algorithm 1, the complexity of step 2 in Algorithm 1 is O ( n 2 ) , step 3 is O ( n 3 ) , the complexity of steps 1,4,5,6 is O ( n ) . So the complexity of Algorithm 1 is O ( n 3 ) .

Acknowledgements

Hsu was supported by the Ministry Science and Technology of Taiwan under Grant MOST 106-2221-E-252-003.

Cite this paper: Geng, X. , Wang, J. and Hsu, C. (2018) Flow Shop Scheduling Problem with Convex Resource Allocation and Learning Effect. Journal of Computer and Communications, 6, 239-246. doi: 10.4236/jcc.2018.61024.
References

[1]   Vickson, R.G. (1980) Two Single Machine Sequencing Problems Involving Controllable Job Processing Times. AIIE Transactions, 3, 258-262. https://doi.org/10.1080/05695558008974515

[2]   Biskup, D. (1999) Single-Machines Scheduling with Learning Con-siderations. European Journal of Operational Research, 115, 173-178. https://doi.org/10.1016/S0377-2217(98)00246-X

[3]   Wang, D., Wang, M.Z. and Wang, J.B. (2010) Single-Machine Scheduling with Learning Effect and Resource-Dependent Processing Times. Computers & Industrial Engineering, 59, 458-462. https://doi.org/10.1016/j.cie.2010.06.002

[4]   Shabtay, D. and Kaspi, M. (2004) Minimizing the Total Weighted Flow Time in a Single Machine with Controllable Processing Times. Computers & Operations Research, 31, 2279-2289. https://doi.org/10.1016/S0305-0548(03)00187-4

[5]   Leyvand, Y., Shabtay, D. and Steiner, G. (2010) A Unified Approach for Scheduling with convex Resource Consumption Functions Using Positional Penalties. European Journal of Operational Research, 206, 301-312. https://doi.org/10.1016/j.ejor.2010.02.026

[6]   Zhu, Z., Sun, L., Chu, F. and Liu, M. (2011) Single-Machine Group Scheduling with Resource Allocation and Learning Effect. Computers & Industrial Engineering, 60, 148-157. https://doi.org/10.1016/j.cie.2010.10.012

[7]   Wang, J.B. and Wang, J.J. (2015) Research on Scheduling with Job-Dependent Learning Effect and Convex Resource Dependent Processing Times. International Journal of Production Research, 53, 5826-5836. https://doi.org/10.1080/00207543.2015.1010746

[8]   Liu, Y. and Feng, Z. (2014) Two-Machine No-Wait Flow Shop Scheduling with Learning Effect and Convex Resource-Dependent Processing Times. Computers & Industrial Engineering, 75, 170-175. https://doi.org/10.1016/j.cie.2014.06.017

[9]   Lu, Y.Y., Li, G., Wu, Y.B. and Ji, P. (2014) Optimal Due-Date Assignment Problem with Learning Effect and Resource-Dependent Processing Times. Optimization Letters, 8, 113-127. https://doi.org/10.1007/s11590-012-0467-7

[10]   Li, G., Luo, M.L., Zhang, W.J. and Wang, X.Y. (2015) Single-Machine Due-Window Assignment Scheduling Based on Common Flow Allowance, Learning Effect and Resource Allocation. International Journal of Production Research, 53, 1228-1241. https://doi.org/10.1080/00207543.2014.954057

[11]   Yin, N. and Wang, X.Y. (2011) Single-Machine Scheduling with Controllable Processing Times and Learning Effect. Optimization Letters, 54, 743-748. https://doi.org/10.1007/s00170-010-2973-z

[12]   Gao, F., Liu, M., Wang, J.J. and Lu, Y.Y. (2017) No-Wait Two-Machine Permutation Flow Shop Scheduling Problem with Learning Effect, Common Due Date and Controllable Job Processing Times. International Journal of Production Research. https://doi.org/10.1080/00207543.2017.1371353

[13]   Graham, R.L., Lawler, E.L., Lenstra, J.K. and RinnooyKan, A.H.G. (1979) Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics, 5, 287-326. https://doi.org/10.1016/S0167-5060(08)70356-X

 
 
Top