Scheduling about a given common due date to minimize mean squared deviation of completion times

  • Published on
    21-Jun-2016

  • View
    216

  • Download
    2

Transcript

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH ELSEVIER European Journal of Operational Research 88 (1996) 328-335 Theory and Methodology Scheduling about a given common due date to minimize mean squared deviation of completion times Xiaohua Weng, Jose A. Ventura* Department of Industrial and Management Systems Engineering, 207 Hammond Building, The Pennsyloania State Unioersity, Unioersity Park, PA 16802, USA Received March 1993 Abstract In this paper the problem of minimizing the mean squared deviation (MSDP) of job completion times about a given common due date in n-job, single-machine scheduling is considered. The release times for all jobs are assumed to be zero. No polynomial time algorithms have been found to identify an optimal solution to MSDP. For the tightly restricted version of MSDP, no even pseudo-polynomial time algorithms have been found to identify an optimal solution. We present some dominance properties for MSDP based on which a pseudo-polynomial dynamic programming algorithm which is an extension of the dynamic programming algorithm proposed by Lee, Danusaputro and Lin is presented to optimally solve the tightly restricted version of MSDP. Computational results show that the proposed dynamic programming algorithm can optimally solve tightly restricted instances of MSDP with up to 100 jobs in less than two seconds. Keywords: Production/scheduling: Minimizing mean squared deviation; Dynamic programming: Exact algorithm O. Introduction In nonpreemptive n-job single-machine sched- uling, the mean squared deviation problem (MSDP) is to schedule all the jobs about a given common due date d so as to minimize the mean squared deviation of job completion times from the common due date. MSDP was first introduced by Bagchi, Sullivan and Chang (1987). This objective is important in certain environments and consistent with the current emphasis on the just-in-time production * Corresponding author. philosophy. For a historical perspective on MSDP and related applications, refer to Bagchi, Sullivan and Chang (1987), or Vani and Raghavachari (1987). For other scheduling problems involving earliness and tardiness penalties, refer to such excellent review paper as by Baker and Scudder (1990). The solution strategy for MSDP depends on the size of d with respect to the job processing times. When d is sufficiently large, MSDP is called unrestricted and shown by Bagchi, Sullivan and Chang (1987) to be equivalent to the com- pletion time variance problem (CTVP) which was introduced by Merten and Miller (1972) and has 0377-2217/96/$09.50 ~) 1996 Elsevier Science B.V. All rights reserved SSD1 0377-2217(94)00195-2 X. Weng, J.A. Ventura / European Journal of Operational Research 88 (1996) 328-335 329 attracted significant attention (De, Ghosh and Wells, 1992; Eilon and Chowdhury, 1977; Gupta, Gupta and Bector, 1990; Hall and Kubiak, 1991; Kanet, 1981; Kubiak, 1992; Schrage, 1975). When d is sufficiently small, MSDP is called tightly restricted (De, Ghosh and Wells, 1989). When d is neither large nor small, MSDP is called restricted. Rigorous definitions of unrestricted, restricted and tightly restricted versions of MSDP are given in the next section. MSDP has recently been shown to be NP-complete by Kubiak (1992). Both the restricted and unrestricted versions of MSDP can be solved by algorithms that can solve CTVP (De, Ghosh and Wells, 1990). For the tightly constrained version of MSDP, how- ever, there exist only heuristic algorithms (De, Ghosh and Wells, 1990, Eilon and Chowdhury, 1977) and enumerative algorithms (Bagchi, Sulli- van and Chang, 1987; Eilon and Chowdhury, 1977). The latter are inadequate for solving large instances of MSDP (i.e., more than 40 jobs). The primary objective of this paper is to find an efficient procedure to solve the tightly restricted version of MSDP. In Section 1, some dominance properties are presented. Based on these domi- nance properties, a pseudo-polynomial dynamic programming algorithm is proposed in Section 2 to optimally solve the tightly restricted version of MSDP. Section 3 provides some computational results. Some concluding remarks are presented in Section 4. o'. When no ambiguity should occur, Ci(~r) will be simply written as C,. Let p~ be the processing time of job Ji, i = 1, 2 . . . . , n. Without loss of generality, assume that 0 ~< p~ ~< P2 ~< ~< p,. The make span is MS = E Pi . iEN Let s~ and Ci be, respectively, the start and com- pletion times of job Ji in a sequence, i = 1,2 . . . . ,n. A sequence is called o-about-d if jobs com- pleted on or before d are in longest processing time first (LPT) order and jobs started on or after d are in shortest processing time first (SPT) order. A sequence is called v-shaped if jobs completed before job Jt are in LPT order and jobs started after job JL are in SPT order. Property 1. For any given instance of MSDP, f(d) is a non-increasing function of the common due date d. Proof. Assume that f (d) is not a non-increasing function of the common due date d, i.e., there exist d~ and d2 such that dl < d2 but f (d0 < f(d2). Let ~* and cr~ be the optimal schedules corre- sponding to common due dates d~ and d2, respec- tively. By definition (1), f(dO = 1 ~ [C,(o-*) - d~] Ni~N and 1. Dominance properties for MSDP Let f (d) denote the optimal objective value for MSDP at the common due date d. Then, MSDP can mathematically be stated as follows: f (d) = min v(o', d) o-El l = 1 E [C,(oO - d)l 2, (1) HiEN where II is the set of all the sequences generated out of the n jobs, N is the set {1, 2 . . . . . n} and Ci (tr) is the completion time of job Ji in sequence f (d2) = 1_ ~, [C,(cr~') - d2]. n i~N However, if denoting by o-' the schedule obtained from delaying the schedule tr~ by d2- dl, we must have Ci = (o" ) = C i (o ' * ) + (d2 - d , ) , for all i, and v(o-', d2) = 1 ~ [C,(cr') - d=] 2 n i~N = 1 E {[C i (o ' t ) + (d2 - dO] - d2} 2 n i~N 330 X. Weng, J.A. Ventura / European Journal of Operational Research 88 (1996) 328-335 = lni~N ~ [Ci('l~) -- dl]2 eI = f(d,) < f(d2), which implies the contradiction that o-* is not optimal. [] Let (Bagchi, Sullivan and Chang, 1987; De, Ghosh and Wells, 1989): d** = max{d :f(dl) >f(d2) if as < a2 ~< d}, d* = min{d : f (d l ) = f(d2) if dl =/= d2 and d,, d2>~d}. Then, f (d) is strictly decreasing if d ~< d** and constant for all d/> d*. Fig. 1 shows the function f (d) of an example problem where n = 3 and (pl,p2,p3) = (2, 5, 44). For this example prob- lem, d** = 21 and d* = 47. The MSDP is tightly restricted, restricted and unrestricted, if d~x. Weng, J.A. Ventura I European Journal of Operational Research 88 (1996) 328-335 331 the common due date d, and E and T are, respec- tively, the subsequences of jobs completed before and started after job Jd. Thus, jobs in E (T) must be completed before (started after) d. By Property 3, jobs in subsequence E (T) are in LPT (SPT) order. If job Jd is job J~, the property holds. If job Ja is not job J1 but is started on d, Property 3 implies that subsequence (Ja, T) must be in SPT order. Then the last job in E must be job J~ and, therefore, the property holds for this case. The property can be similarly shown for the case that job Ja is not job J1 but is completed on d. Now, it remains to show that the property also holds if job Ja is not job J~, and started before and completed after d. Then, job J~ must be either the last job in E or the first job in T. Assume that J~ is the last job in E. Let JTa be the first job in T. Then, it is necessary to show that Pa 332 X. Weng, J.A. Ventura / European Journal of Operational Research 88 (1996) 328-335 0 d MS r-llr-21 .- Ill Ir [ r+l [ "-- [ n [ Fig. 3. Sequence ~rn. 0 d MS Fig. 4. Sequence ~Q. The upper bounds on Ci can be similarly proven by using the sequence o-o shown in Fig. 4. [] Property 8 implies that to identify an optimal solution for the tightly restricted version of MSDP, we only have to consider the sequences where job Ji is started on or after d -pr - P i , and completed on or before d + pq + P i . 2. Dynamic programming solution For the restricted and unrestricted versions of MSDP, optimal solutions can be obtained by using algorithms that can solve CTVP (De, Ghosh and Wells, 1990), such as the pseudo-poly- nomial dynamic programming algorithm of De, Ghosh and Wells (1992). For the tightly restricted version of MSDP, only heuristic and total enu- merative algorithms are available in the litera- ture. In this section, we propose an efficient pseudo-polynomial dynamic programming algo- rithm to optimally solve the tightly restricted ver- sion of MSDP. Our algorithm is an extension of the dynamic programming algorithm proposed by Lee, Danusaputro and Lin (1991) for solving a single machine scheduling problem with a linear penalty objective function. By Property 6, jobs in any optimal schedule have to be continuously processed. Property 3 and Property 5 imply that we only have to con- sider zero-start-time v-shaped sequences to iden- tify an optimal solution. In the following dynamic programming algo- rithm, we start with job J1 and build up v-shaped partial sequences by successively scheduling the shortest one of the remaining jobs, with a given start time of the first job in the partial sequences. Since only v-shaped sequences have to be con- sidered, the next job to be scheduled has to imme- diately either proceed or succeed the partial se- quences at the previous stage. Let s~ = max{0, d - Pr - Pk}, s~ = min{MS - Pk, d + pq + P~ - p,}. for k = 1, 2 . . . . . n. By Properties 7 and 8, s~ and s~ are, respectively, the lower and upper bounds on the start time of the first job in the partial sequences, including the k shortest jobs, that have to be considered. Dynamic Programming (DP) Algorithm Optimal value function: F (k , s) = The minimum total cost if the k shortest jobs have been scheduled, given that s is the start time of the first job in partial sequences including the k shortest jobs. Recursioe relations: For k=2,3 . . . . . n and s=s l , s~+l , s~ + 2 . . . . . s~, F(k , s) = min~'F(k - 1, s + Pk) + (S + Pk -- d) 2, (2) [V (k 1, s) + (s + Pk -- d) z. (3) In the case of a tie, the tie is broken arbitrarily. Optimal policy function: P(k, s) ={10 (4) if job k is scheduled in the front, if job k is scheduled at the back. Boundary conditions: F(1, s) = (s + p, - d) z, L L s=s~,s l +1, s~+2 . . . . . Sl ~. F(k ,s )=w for eachkEN, s s~. Optimal solution: Optimal objective value = F(n, 0). (5) (6) (7) X. Weng, J.A. Ventura I European Journal of Operational Research 88 (1996) 328-335 333 Optimal sequence: (P(n, s . ) , P (n - 1, s . _ 1) . . . . . P(1, sl)), (8) where sn = 0 and Sk = Sk + L + P (k + 1, sk + 1)Pk + 1, k=n- l ,n -2 . . . . . 2,1. (9) Sk is the start time of the first job in the k shortest job partial sequence of the optimal sequence. Theorem 1. The sequence obtained by the DP A lgor i thm is opt imal to the tightly restricted ver- s ion o f MSDP. Proof. By Properties 5 and 6, any optimal se- quence has to be a v-shaped one without inserted idle time. Assume that the k - 1 shortest jobs have been scheduled and job J~, is the next job to be scheduled. Then job Jk has to be scheduled to immediately proceed or succeed the partial sequence at the previous stage with the start time s given. If job Jk is scheduled to precede the partial sequence o-~_ ~ from the previous stage (see Fig. 5), the total cost is the cost of job Jk (starting at time s) plus the minimum total cost of the partial sequence at the previous stage with start time s + Pk, which yields (2). If job Jk is scheduled to succeed the partial sequence trk_ from the previous stage (Fig. 6), the total cost is the cost of job J~ (starting at time s + Pk- 1) plus the minimum total cost of the partial sequence at the previous stage with start time s, which yields (3). Since the start time of the first job of any optimal sequence has to be zero, (7) and (8) give the optimal solution. [] Since at each stage of the DP Algorithm, the I Ikl ok_l I I 0 s d MS Fig. 5. Job Jk is assigned preceding t rk - 1" I o ,_1 I k I I s d MS Fig. 6. Job Jk is assigned succeeding tr~ _ 1. start times (of the first job in a partial sequence) that have to be considered are non-negative inte- gers and less than MS (=~ieNP i ) , the compu- tational complexity of the DP Algorithm is O(n~ieNP i ) . 3. Computational study A computational study has been undertaken to test the performance of the proposed DP Algo- rithm. The DP Algorithm is coded in FORTRAN and run on a VAX-8550 machine. The execution times for the test problems are recorded in CPU seconds, excluding input and output times. All the test problems are randomly generated as follows. A uniform random number generator RAN(iseed) with iseed = 1059 is used to create a value uniformly distributed in (0, 1). This value times an integer U generates a new value in (0, U). Then, by taking the integer part of this new value plus 1 (since it does not make any sense to include a job with zero processing time), we obtain a random integer number uniformly distributed in [1, U]. For each n, we generate a sequence of random integer numbers from which the first n numbers are taken as the first problem, the second n numbers as the second problem, and SO on . Table 1 reports the minimum, average and maximum CPU times for n -- 20, 40, 60, 80 and 100. For all the n tested, U is set to be equal to 100. Twenty problems are tested for each n. For every tested problem, since MS is always less than the lower bound on d** provided by Pro- perty 2, the common due date d is chosen to be the integer part of 1MS. Therefore, it is guaran- Table 1 Computational results for the DP Algorithm CPU time (seconds) n Minimum Average Maximum 20 0.03 0.05 0.07 40 0.21 0.24 0.27 60 0.51 0.58 0.72 80 0.99 1.07 1.23 100 1.59 1.74 1.94 334 X. Weng, J.A. Ventura I European Journal of Operational Research 88 (1996) 328-335 teed that all the problems tested are instances of the tightly restricted version of MSDP. The computational results show that the DP Algo- rithm can solve tightly restricted instances of MSDP with up to 100 jobs in less than 2 seconds, while it takes, on the average, more than 3 CPU minutes for the branch and bound algorithm of De, Ghosh and Wells (1990) to produce solutions with 40 jobs. 4. Concluding remarks We have provided a pseudo-polynomial solu- tion to the tightly restricted version of MSDP for which no polynomial or pseudo-polynomial time algorithms are previously known to be available. The computational results show that the DP Al- gorithm proposed in this paper can optimally solve tightly restricted instances of MSDP with up to 100 jobs in less than two seconds. The proposed DP Algorithm can be extended to solve CTVP as follows. Since changing start time of a schedule will not affect the variance of the schedule, it is only necessary to consider zero start time schedules for identifying an optimal schedule to CTVP. Ventura and Weng (1993) showed that for every instance of CTVP, there is an optimal schedule or* such that (MS + p , - p , _ 1) ~ ~[~(Or*) ~ (MS + p,) . They also showed that an optimal solution to MSDP is optimal to CTVP if d = (~(o-*), where or* is an optimal schedule to CTVP. In addition, Bagchi, Sullivan and Chang (1987) proved that for any given schedule o-, the mean squared devi- ation of job completion times from d is minimized if d = C(cr). The combination of the above results implies that if we try every d that is equal to a possible mean completion time [[](O') ~ [I(Ms + Pn - Pn -- 1), 1( MS + Pn) ] and run the DP Algorithm to obtain an optimal solution, then, of these optimal solutions, the one with the minimum objective value is optimal to CTVP. Since the mean completion time of any schedule with start time zero is a multiplier of 1/n, d = (MS + p,, - p,, _ 1) + k/n, k=0,1 ,2 . . . . . n 'p , , -1 , include all the mean completion times that have to be considered. Similarly, the DP Algorithm can also be extended to solve the restricted ver- sion of MSDP, by considering every d=d**+k/n , n =0,1 ,2 . . . . . n(d -d** ) . In practice, d** is replaced by the lower bound on d** provided by Property 2, because there are no known methods for determining d**. An instance of MSDP may be tightly restric- ted, restricted and unrestricted, depending upon the size of the common due date d with respect to the job processing times of the instance. Tightly restricted, restricted and unrestricted versions of MSDP require different approaches for finding an optimal schedule (De, Ghosh and Wells, 1990). As mentioned in Section 2, however, the restricted version of MSDP may vanish (i.e., d** = d*) for some instances of MSDP. No ef- ficient methods are known available for deter- mine d** and d* for a given instance of MSDP. If d* can be determined, then the DP Algorithm can solve CTVP by letting d = d*. Acknowledgement This work was partially supported by the National Science Foundation under Grant DDS 90-57066. References Bagchi, U., Sullivan, R.S., and Chang, Y.L. (1987), "Mini- mizing mean squared deviation of completion times about a common due date", Management Science 33, 894-906. Baker, K.B., and Scudder, G.D. (1990), "Sequencing with earliness and tardiness penalties: A review", Operations Research 38, 22-36. De, P., Ghosh, J.B., and Wells, C.E. (1989), "A note on the minimization of mean squared deviation of completion times about a common due date", Management Science 35, 1143-1147. De, P., Ghosh, J.B., and Wells, C.E. (1990). "Scheduling about a common due date with earliness and tardiness X. Weng, J.A. Ventura I European Journal of Operational Research 88 (1996) 328-335 335 penalties", Computers & Operations Research 17, 231- 241. De, P., Ghosh, J.B., and Wells, C.E. (1992), "On the mini- mization of completion time variance with a bicriteria ex- tension", Operations Research 40, 1138-1155. Eilon, S., and Chowdhury, I.G. (1977), "Minimizing waiting time variance in the single machine problem", Manage- ment Science 23, 567-575. Gupta, M.C., Gupta, Y.P., and Bector, C.R. (1990), "Mini- mizing the flow-time variance in single-machine systems", Journal of the Operational Research Society 41,767-779. Hall, N.G., and Kubiak, W., (1991), "Proof of a conjecture of Schrage about the completion time variance problem", Operations Research Letters 10,467-472. Kanet, J.J. (1981), "Minimizing variation of flow time in sin- gle machine systems", Management Science 27, 1453-1459. Kubiak, W. (1992), "Completion time variance problem on single machine is difficult", Working Paper, Faculty of Business Administration, Memorial University of New- foundland, St. John's, A1B 2X5, Canada. Lee, C.Y., Danusaputro, S.L., and Lin, C.S. (1991), "Mini- mizing weighted number of tardy jobs and weighted ear- liness-tardiness penalties about a common due date", Computers & Operations Research 18, 379-389. Merten, A.G., and Muller, M.E. (1972), "Variance minimi- zation in single machine sequencing problem", Manage- ment Science 18, 518-528. Schrage, L. (1975), "Minimizing the time-in-system variance for a finite jobset", Management Science 21,540-543. Vani, V., and Raghavachari, M. (1987), "'Deterministic and random single machine sequencing with variance minimi- zation", Operations Research 135, 111-120. Ventura, J. A., and Weng, X. (1993), "Minimizing the single machine completion time variance", IMSE Working Paper 93-112, Dept. of Industrial and Management Systems En- gineering, Penn State University, University Park.

Recommended

View more >