Single machine scheduling with randomly compressible processing times

  • Published on

  • View

  • Download


<ul><li><p>This article was downloaded by: [Nova Southeastern University]On: 07 October 2014, At: 14:27Publisher: Taylor &amp; FrancisInforma Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House,37-41 Mortimer Street, London W1T 3JH, UK</p><p>Stochastic Analysis and ApplicationsPublication details, including instructions for authors and subscription information:</p><p>Single machine scheduling with randomly compressibleprocessing timesX. D. Qi , G. Yin a &amp; J. R. Birge ba Department of Mathematics , Wayne State University , Detroit, MI, 48202, U.S.A.b McCormick School of Engineering and Applied Science , Northwestern University ,Evanston, IL, 60208, U.S.A.Published online: 15 Feb 2007.</p><p>To cite this article: X. D. Qi , G. Yin &amp; J. R. Birge (2002) Single machine scheduling with randomly compressible processingtimes, Stochastic Analysis and Applications, 20:3, 591-613</p><p>To link to this article:</p><p>PLEASE SCROLL DOWN FOR ARTICLE</p><p>Taylor &amp; Francis makes every effort to ensure the accuracy of all the information (the Content) containedin the publications on our platform. However, Taylor &amp; Francis, our agents, and our licensors make norepresentations or warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of theContent. Any opinions and views expressed in this publication are the opinions and views of the authors, andare not the views of or endorsed by Taylor &amp; Francis. The accuracy of the Content should not be relied upon andshould be independently verified with primary sources of information. Taylor and Francis shall not be liable forany losses, actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoeveror howsoever caused arising directly or indirectly in connection with, in relation to or arising out of the use ofthe Content.</p><p>This article may be used for research, teaching, and private study purposes. Any substantial or systematicreproduction, redistribution, reselling, loan, sub-licensing, systematic supply, or distribution in anyform to anyone is expressly forbidden. Terms &amp; Conditions of access and use can be found at</p><p></p></li><li><p>SINGLE MACHINE SCHEDULING WITHRANDOMLY COMPRESSIBLE</p><p>PROCESSING TIMES</p><p>X. D. Qi,1 G. Yin,2,* and J. R. Birge3</p><p>1TAC Automotive Group, 500 Town Center Dr., Suite 100,</p><p>Dearborn, MI 481262Department of Mathematics, Wayne State University,</p><p>Detroit, MI 482023McCormick School of Engineering and Applied Science,</p><p>Northwestern University, Evanston, IL 60208</p><p>ABSTRACT</p><p>This work is concerned with single machine scheduling with</p><p>random compression of processing times. The objective is to find</p><p>the optimal sequence to minimize the cost based on earliness,</p><p>tardiness and compression. The analysis is carried out under a</p><p>common due date. Both absolute derivation cost and squared</p><p>derivation cost are considered. For both constrained problems and</p><p>unconstrained problems, it is shown that an optimal schedule must</p><p>be V-shaped. Remarks on common slack model is also provided.</p><p>Key Words: Scheduling; Random compression; Earliness;</p><p>Tardiness; Due date; V-shaped sequence</p><p>591</p><p>Copyright q 2002 by Marcel Dekker, Inc.</p><p>*Corresponding author. E-mail:</p><p>STOCHASTIC ANALYSIS AND APPLICATIONS, 20(3), 591613 (2002)</p><p>Dow</p><p>nloa</p><p>ded </p><p>by [</p><p>Nov</p><p>a So</p><p>uthe</p><p>aste</p><p>rn U</p><p>nive</p><p>rsity</p><p>] at</p><p> 14:</p><p>27 0</p><p>7 O</p><p>ctob</p><p>er 2</p><p>014 </p></li><li><p>1. INTRODUCTION</p><p>The sweeping changes produced by computer-based technologies have a</p><p>significant impact on management of manufacturing systems; see for example,[28] and the references therein. Owing to these changes, due-date assignment and</p><p>scheduling problems in which the jobs have compressible processing times has</p><p>received much attention lately.</p><p>The concept of compressible processing time was originated from the area of</p><p>project planning and control; see, for example [15], among others. The motivation in</p><p>the field of scheduling is of the same spirit. Increasing manufacturing flexibility is a</p><p>key to improving responsiveness. In particular, production volume flexibility has</p><p>long been a corporate goal in cyclical industries. Nowadays, it is well recognized that</p><p>the ability to use trial-and-error to tune the performance of a system is virtually</p><p>useless on an environment in which changes occur faster than the lessons can be</p><p>learned. Optimal scheduling and rescheduling after changes in parameters or</p><p>constraints are of critical importance. This is a greater need for understanding on</p><p>compressible processing times, and their effect. In many manufacturing systems,</p><p>jobs can be accomplished in shorter or longer durations by increasing or decreasing</p><p>additional resources. Not only the use of compressible processing times is justified,</p><p>but also it provides more realistic models. Studies on problems with compressible</p><p>processing times was initiated by [25,26]. A survey along the line of scheduling is</p><p>in [19]. To mention some of the recent progress on this problem, we cite the work[11,13,18,24,27]. More recently, [1], [8], and [20] extend the problem to include the due-</p><p>date aspect. To be more specific, in [20], the authors consider the common due-date</p><p>assignment and single-machine scheduling problem in which the objective function</p><p>is the sum of penalties based on earliness, tardiness and processing time</p><p>compressions. The main idea is to reduce the underlying problem to an assignment</p><p>problem. The authors of [1] extend the results of [20] to the parallel-machine</p><p>scheduling case. The reference [8] further generalizes the result to the case where the</p><p>cost of compression is a general convex function of the amount of compression.</p><p>In [12], we consider a due-date assignment and single-machine scheduling problem in</p><p>which a penalty for due-dates is added to the objective function which includes the</p><p>penalties for earliness, tardiness and processing time compressions. The objective is</p><p>to determine jointly the optimal due-dates, the optimal sequence, and the optimal</p><p>processing time compressions to minimize the total penalty. Again, the key point is</p><p>to reduce the underlying problem to an assignment problem. The paper [9] presents a</p><p>single-machine scheduling model in which the job processing times are controllable</p><p>with linear costs. Solutions of a dynamic programming algorithm and a fully</p><p>approximation scheme for the problem are obtained.</p><p>All of the aforementioned research to date has been concerned with</p><p>deterministic compressible times. To the best of our knowledge, the case of</p><p>random compressible times have not received much attention. However, more</p><p>QI, YIN, AND BIRGE592</p><p>Dow</p><p>nloa</p><p>ded </p><p>by [</p><p>Nov</p><p>a So</p><p>uthe</p><p>aste</p><p>rn U</p><p>nive</p><p>rsity</p><p>] at</p><p> 14:</p><p>27 0</p><p>7 O</p><p>ctob</p><p>er 2</p><p>014 </p></li><li><p>often than not, the deterministic formulation alone does not reflect the reality</p><p>well. Job processing time compressions are usually unknown in advance, are</p><p>unavoidably to include uncertainty, and cannot be predicted before hand. In this</p><p>work, we formulate the single-machine scheduling problem as one that job</p><p>processing times are randomly compressible. The objective is to find the optimal</p><p>job sequence or the optimal due dates to minimize the total penalty based on the</p><p>job earliness/tardiness and compressions. Common due-date-assignment method</p><p>and common slack-due-date-assignment method are used to assign due dates to</p><p>jobs. The analysis is carried out under the assumption that the compressions are</p><p>independent and identically distributed random variables.</p><p>The rest of the paper is arranged as follows. Section 2 presents the problem</p><p>description and modeling. Section 3 discusses the relationship between V-shaped</p><p>optimal sequence and the monotone-about-T property of the cost function.</p><p>Section 4 deals with the absolute derivation objective function. Both</p><p>continuously distributed random compressions and discrete ones are considered.</p><p>Section 5 treats the squared derivation objective function. Some remarks on the</p><p>common slack model are given in section 6. Conclusion and topics for further</p><p>study are discussed in section 7.</p><p>2. PROBLEM FORMULATION</p><p>This work considers a single-machine scheduling problem involving n jobs</p><p>with the due-dates dj, for j 1; 2; . . .; n: A job j has a deterministic processingtime pj, which can be compressed by an amount zj, 1 # j # n: Here zj is a randomvariable and 0 # zj # zj: So the actual processing time of job j is pj 2 zj: Weassume that zj , pj; 1 # j # n: This condition is necessary because if there is ajob j such that zj pj; then it may be compressed to have zero processing timewhich is not reasonable in practice.</p><p>We assume that all the jobs are ready at time zero and no pre-emption is</p><p>allowed. Let Rj, Ej and Tj denote the actual completion time, the earliness and the</p><p>tardiness of job j, respectively. Then</p><p>Ej max0; dj 2 Rj and Tj max0;Rj 2 dj:Let S denote the job sequence and d the vector of due dates, that is,</p><p>~d d1; d2; . . .; dn: We are interested in the following two models:(1) Model 1: The objective function is of the form</p><p>JS; ~d EXnj1</p><p>aEj bTj bzj; 1</p><p>SINGLE MACHINE SCHEDULING 593</p><p>Dow</p><p>nloa</p><p>ded </p><p>by [</p><p>Nov</p><p>a So</p><p>uthe</p><p>aste</p><p>rn U</p><p>nive</p><p>rsity</p><p>] at</p><p> 14:</p><p>27 0</p><p>7 O</p><p>ctob</p><p>er 2</p><p>014 </p></li><li><p>where a, b and b are positive real numbers representing unit penaltiesfor earliness, tardiness and compression, respectively.</p><p>(2) Model 2: The objective function has the following form.</p><p>JS; ~d EXnj1</p><p>aRj 2 dj2 bzj; 2</p><p>where a and b are positive real numbers representing unit penaltiesfor earliness/tardiness and compression, respectively.</p><p>The problem is to determine the optimal sequence S*, or the optimal</p><p>due-date vector d* or both to minimize the function J(S, d ). If the duedates are given and fixed, the problem is called constrained. If the due dates</p><p>are decision variables and to be determined, then the problem is called</p><p>unconstrained.</p><p>Let Cj denote the deterministic completion time of job j, which is sequence</p><p>dependent. Define C0 0: Without loss of generality, we assume that Cj is thecompletion time of job j for a fixed sequence which can be taken as S {1; 2; . . .; n}: Then,</p><p>Cj Xji1</p><p>pi:</p><p>Consequently, we have</p><p>Rj Xji1</p><p>pi 2 zi Cj 2 Zj;</p><p>where</p><p>Zj Xji1</p><p>zi;</p><p>which is the total compression of the first j jobs in the sequence. In this work we</p><p>treat the case where the compressions zj; j 1; 2; . . .; n; are independent andidentically distributed variables. Let zj z; j 1; 2; . . .; n; then</p><p>0 # Zj # jz</p><p>Remark 2.1. We assume that 0 # zj # zj; that is, zj is a bounded randomvariable. This condition is satisfied for example, for random variables following</p><p>uniform distribution or Beta distribution.</p><p>QI, YIN, AND BIRGE594</p><p>Dow</p><p>nloa</p><p>ded </p><p>by [</p><p>Nov</p><p>a So</p><p>uthe</p><p>aste</p><p>rn U</p><p>nive</p><p>rsity</p><p>] at</p><p> 14:</p><p>27 0</p><p>7 O</p><p>ctob</p><p>er 2</p><p>014 </p></li><li><p>3. PRELIMINARY</p><p>We begin with the following deterministic problem. Consider the single</p><p>machine scheduling problem where the objective function is given as</p><p>JS Xnj1</p><p>gCj vj; 3</p><p>where Cj is the completion time of the jth job in the sequence S, g(t ) is a</p><p>continuous function and vj is a constant which does not depend on Cj. So</p><p>gCj vj is the contribution of the jth job. Note that gCj vj also depends onthe due dates for the problems with early-tardy penalties.</p><p>A typical result for problems with early-tardy costs is the V-shaped</p><p>property of the optimal schedule. The concept of V-shaped property was first</p><p>introduced in [14]. To proceed, we recall the definition first.</p><p>Definition 3.1. A sequence is said to be V-shaped with respect to processing</p><p>times if in the sequence the jobs before (resp. after) the job with the shortest</p><p>processing times are arranged in nonincreasing (resp. nondecreasing) order of</p><p>processing times.</p><p>Definition 3.2. A function f(t ) is said to be monotone about T if it is</p><p>nonincreasing for t # T and nondecreasing for t $ T (see [2]).</p><p>Lemma 3.3. If g(t ) is a monotone function about T, then there exists an V-</p><p>shaped sequence that minimizes the cost function (3).</p><p>Proof. The main steps are outlined below. A similar proof may also be found</p><p>in [2].</p><p>Without loss of generality, we may assume the optimal sequence is S {1; 2; . . .; n}: Let S</p><p>denote the sequence obtained by interchanging job j and job</p><p>j 1 in S. Then</p><p>JS2 JS gCj21 pj12 gCj21 pj:</p><p>Consider two consecutive jobs j and j 1 such that pj , pj1 and Cj21 pj1 #T: Note that Cj21 pj , Cj21 pj1 and since the function g(t ) is nonincreasingfor t # T ;</p><p>JS2 JS gCj21 pj12 gCj21 pj , 0:</p><p>SINGLE MACHINE SCHEDULING 595</p><p>Dow</p><p>nloa</p><p>ded </p><p>by [</p><p>Nov</p><p>a So</p><p>uthe</p><p>aste</p><p>rn U</p><p>nive</p><p>rsity</p><p>] at</p><p> 14:</p><p>27 0</p><p>7 O</p><p>ctob</p><p>er 2</p><p>014 </p></li><li><p>Thus, jobs j and j 1 can be interchanged without increasing the objectivefunction. Repeating the above procedure for all such consecutive jobs results in a</p><p>sequence in which all jobs completing by T are ordered in LPT (largest</p><p>processing time) sequence. The same argument can be applied to jobs starting</p><p>after T to show that an SPT (smallest processing time) sequence minimizes the</p><p>contribution to the objective function J(S).</p><p>Note that the resulting sequence need not be V-shaped because the processing</p><p>time of the job that starts before the due-date T and completes after T may be</p><p>longer than that of each of its adjacent jobs. In what follows we show this can not</p><p>be the case, adn conclude the desired V-shaped property.</p><p>Now consider the situation where pj . pj21; pj . pj1 and Cj21 , T ,Cj21 pj: There are three cases.</p><p>(1) Cj21 pj1 . T : Interchanging job j and job j 1; we haveT , Cj21 pj1 , Cj21 pj:</p><p>It follows that</p><p>JS2 JS gCj21 pj12 gCj21 pj , 0;since g(t ) is a nondecreasing function for t . T : Hence we caninterchange job j and job j 1 without increasing the objectivefunction.</p><p>(2) Cj22 pj , T : Let ~S denote the sequence obtained by interchangingjobs j and j 2 1: Then</p><p>Cj22 pj21 , Cj22 pj , T ;which leads to</p><p>J ~S2 JS gCj22 pj2 gCj22 pj21 , 0since g(t ) is a nonincreasing function for t , T : Hence we caninterchange job j and job j 2 1 without increasing the objectivefunction.</p><p>(3) Consider the case where neither case (1) nor case (2) is satisfied, i.e.,</p><p>Cj21 pj1 , T and Cj22 pj . T : First, we havegCj21 pj12 gCj22 pj21 , 0</p><p>since Cj22 pj21 Cj21 , Cj21 pj1 , T and g(t ) is non-increasing for t , T : Similarly,</p><p>gCj22 pj2 gCj21 pj , 0since T , Cj22 pj , Cj21 pj and g(t ) is nondecreasing for t . T :</p><p>QI, YIN, AND BIRGE596</p><p>Dow</p><p>nloa</p><p>ded </p><p>by [</p><p>Nov</p><p>a So</p><p>uthe</p><p>aste</p><p>rn U</p><p>nive</p><p>rsity</p><p>] at</p><p> 14:</p><p>27 0</p><p>7 O</p><p>ctob</p><p>er 2</p><p>014 </p></li><li><p>Thus we have</p><p>JS2 JS J ~S2 JS</p><p> gCj21 pj12 gCj21 pj gCj22 pj</p><p>2 gCj22 pj21</p><p> gCj21 pj12 gCj22 pj21</p><p> gCj22 pj2 gCj21 pj</p><p>, 0:</p><p>Therefore, JS2 JS , 0; or J ~S2 JS , 0 or both.</p><p>Hence, there exists a V-shaped optimal schedule. The proof is complete. A</p><p>Corollary 3.4. If the function g(t ) is convex, then there exists an V-shaped</p><p>sequence that minimize the cost function (3).</p><p>Proof. The conclusion holds because a convex function must be monoton...</p></li></ul>


View more >