- Home
- Documents
- Scheduling || A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times

Published on

08-Jan-2017View

214Download

1

Transcript

A Solvable Case of the One-Machine Scheduling Problem with Ready and Due TimesAuthor(s): Hiroshi Kise, Toshihide Ibaraki and Hisashi MineSource: Operations Research, Vol. 26, No. 1, Scheduling (Jan. - Feb., 1978), pp. 121-126Published by: INFORMSStable URL: http://www.jstor.org/stable/169895 .Accessed: 09/05/2014 20:32Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at .http://www.jstor.org/page/info/about/policies/terms.jsp .JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range ofcontent in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new formsof scholarship. For more information about JSTOR, please contact support@jstor.org. .INFORMS is collaborating with JSTOR to digitize, preserve and extend access to Operations Research.http://www.jstor.org This content downloaded from 195.78.108.131 on Fri, 9 May 2014 20:32:29 PMAll use subject to JSTOR Terms and Conditionshttp://www.jstor.org/action/showPublisher?publisherCode=informshttp://www.jstor.org/stable/169895?origin=JSTOR-pdfhttp://www.jstor.org/page/info/about/policies/terms.jsphttp://www.jstor.org/page/info/about/policies/terms.jspOPERATIONS RESEARCH 0030-364X/78/2601-0121 $01.25 Vol. 26, No. 1, January-February 1978 ? 1978 Operations Research Society of America A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times HIROSHI KISE Kyoto Institute of Technology, Kyoto, Japan TOSHIHIDE IBARAKI and HISASHI MINE Kyoto University, Kyoto, Japan (Received April 1976; accepted June 1977) We consider a class of n-job one-machine scheduling problems with ready time r(i), processing time p(i), and due time d(i) for each job i. Preemption is not allowed, and precedence constraints among jobs are not assumed. For this problem we show that there is a 0(n2)-time algorithm to find a schedule that minimizes the number of tardy jobs, under the assumption that r(i) 122 Kise, Ibaraki, and Mine NP-complete [2, 5] even if all the jobs except one have the same ready time and the same due time. (Thus it is unlikely that this problem has a polynomial time algorithm [1].) There are also other n-job, one-machine scheduling problems with due times that can be solved in polynomial time under appropriate additional assumptions [2-4, 7]. In particular, Lawler [4] generalizes Moore's result to an O(nlogn) algorithm for the case of agreeable weights, where each job i has weight w(i) and p(i) One-Machine Scheduling Problem 123 Main Algorithm to Compute an Optimal Schedule Step 1. Eo0-4O, j*-O and go to Step 2. (a- stands for the assignment operation represented by = in Algol.) Step 2. If j=n, then go to Step 3. Otherwise, j124 Kise, Ibaraki, and Mine LEMMA 2. Let b satisfy F (J-{a) ) _ F(J-{b} ) for each a E J. Then F(J- U-{a3) > F(J-U-{b3) holds for any UC{c I c>a, c~bl. Proof. We may assume that U is a singleton { c3; the general case then immediately follows by induction. Note that for any three subsets of J) X, Y and Z such that (ViE Z)(VijEXUY)(jr(n) and (2) A(4; n)= A(c; n)=p(n) follows. Furthermore, F(J-{1})_?F(J-{n}) implies A (c; 1) < A (c; n) = p (n). Note that A(4; c)+A(c; 1)=A(4; 1)+A(1; c)5A (c; n)+A(1; c), and hence F(J-{1, c})-F(J-{c, n})= A(c; n)- A(c; 1)>A(4; c)-A(1; c). Therefore, the lemma is proved if A *; c) >- t(1; c) (5) always holds. To prove (5), first assume that n=c+1. Then F(J-{c, n})=F(S,-i)> r(n) > r(c) by assumption, and hence A(c; c) =max {F(Sci1)+p(c), r(n)} -max {F(Sc-1), r(n)} A (1; c) = max f max [F(Sc-, - f1 ), r(c) ]+p (c), r(n)}I -max {F(Sc-l-{ 1} ), r(n)} =max {max [F(Sc1-{1}), r(c)]+p(c), r(n)} -max {max [F(S01-{1}), r(c)], r(n)} holds by (2), where Sj={l, * , j}. Then A(c; c)>A(1; c) immediately follows since A(s) =max {s+p, r(n)} -max {s, r(n)} is obviously non- decreasing in s and F(Sc-1) _ max [F(S01-{ 1} ), r(c) ] holds. The general case n ? c+1 is then proved by induction. Let An-i(x; y) denote A (x; y) for J = {1, *,n-1}. In this case we have A(c; c) =max {F(Snl), r(n)} -max {F(Sn~-{c}), r(n)} =max {F(Sn1), r(n)} -max {F(S.-,)-An- (c; c), r(n)} =max {O, min [Ain-, (; c), F(Sn-1)-r(n)]} A(1; c)=max {O, min [A 1(; c), F(S,,,-{1})-r(n)]}. Now A(c; c)>A(1; c) follows from An-1(40; c)->A-n1(1; c) (induction hypothesis) and F( S,,-) > F(Sn-1- { 1} ) This content downloaded from 195.78.108.131 on Fri, 9 May 2014 20:32:29 PMAll use subject to JSTOR Terms and Conditionshttp://www.jstor.org/page/info/about/policies/terms.jspOne-Machine Scheduling Problem 125 LEMMA 3. For all k, j with 1? k d(k) and l E E. LetSk={1,* ,k}and EnSk = EklU{k} -X. (6) Then X(C Sk) Al) since Ek-lU{k} is not feasible by assumption. We show that E -E U fij- I1}, (7) where i is the smallest element in X, is also j-optimal. Clearly, E and E' have the same cardinality and E nSkCEklU{k}-{l} (by ECEklU {k, k+1, *, j} and iEEk1U{k}) =Ek. These imply that E'fnSk is feasible (since Ek is feasible by Lemma 1). Hence showing F(E'nSk) JEjE11. Now assume that F(Ej_1Ut j} ) >d (j). Then a j-optimal set is a proper subset of Ej-1U I j} This content downloaded from 195.78.108.131 on Fri, 9 May 2014 20:32:29 PMAll use subject to JSTOR Terms and Conditionshttp://www.jstor.org/page/info/about/policies/terms.jsp126 Kise, Ibaraki, and Mine by infeasibility of Ej_1U{j} and by Lemma 3 with k=j-1. Hence Ej= Ej_1Uj}j-{l} is j-optimal since Ej is feasible by Lemma 1, and IE'j= Ej_jU~j} I-1. ACKNOWLEDGMENT The authors wish to thank Professor T. Hasegawa of Kyoto University for his comments. They are also grateful to one of the anonymous referees for his many suggestions, which were quite helpful in improving read- ability and shortening the proofs, and for his having informed us of refer- ences [4, 5]. REFERENCES 1. R. M. KARP, "Reducibility among Combinatorial Problems," in Complexity of Computer Computations, pp. 85-103, R. E. Miller and J. W. Thatcher (Eds.). Plenum Press, New York, 1972. 2. H. KISE, T. IBARAKI, AND H. MINE, "n-Job One-Machine Scheduling Problems with Ready and Due Times," Working Paper, Dept. of Applied Math. and Physics, Kyoto University, Kyoto Japan, 1975; also presented at the XXII International TIMS Meeting, Kyoto, July 1975. 3. E. L. LAWLER, "Sequencing Problems with Deferral Costs," Management Sci. 11, 280-288 (1964). 4. E. L. LAWLER, "Sequencing to Minimize the Weighted Number of Tardy Jobs," Rev. Franz. Automat. Informa. Rech. Opnelle. 10.5 Suppl., 27-33 (1976). 5. J. K. LENSTRA, A. H. G. RINNooY KAN, AND P. BRUCKER, "Complexity of Machine Scheduling Problems," Ann. Discrete Math. 1, 343-362 (1977.) 6. J. M. MOORE, "Sequencing n Jobs on One Machine to Minimize the Number of Tardy Jobs," Management Sci. 15, 102-109 (1968). 7. J. B. SIDNEY, "An Extension of Moore's Due Date Algorithm," in Symposium on the Theory of Scheduling and Its Applications, pp. 393-298, S. E. Elmagh- raby (Ed.). Springer-Verlag, Berlin, 1973. This content downloaded from 195.78.108.131 on Fri, 9 May 2014 20:32:29 PMAll use subject to JSTOR Terms and Conditionshttp://www.jstor.org/page/info/about/policies/terms.jspArticle Contentsp. 121p. 122p. 123p. 124p. 125p. 126Issue Table of ContentsOperations Research, Vol. 26, No. 1, Scheduling (Jan. - Feb., 1978), pp. vii-xvi+i-vi+1-208Volume Information [pp. xi - xvi]Front Matter [pp. vii - vi]Preface [pp. 1 - 2]Performance Guarantees for Scheduling Algorithms [pp. 3 - 21]Complexity of Scheduling under Precedence Constraints [pp. 22 - 35]Flowship and Jobshop Schedules: Complexity and Approximation [pp. 36 - 52]A General Bounding Scheme for the Permutation Flow-Shop Problem [pp. 53 - 67]Minimal Resources for Fixed and Variable Job Schedules [pp. 68 - 85]The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling [pp. 86 - 110]Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related Tasks [pp. 111 - 120]A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times [pp. 121 - 126]On a Real-Time Scheduling Problem [pp. 127 - 140]Scheduling to Minimize Maximum Cumulative Cost Subject to Series-Parallel Precedence Constraints [pp. 141 - 158]The Single-Plant Mold Allocation Problem with Capacity and Changeover Restrictions [pp. 159 - 165]An Algorithm for the Space-Shuttle Scheduling Problem [pp. 166 - 182]Scheduling Boats to Sample Oil Wells in Lake Maracaibo [pp. 183 - 196]Technical NotesA New Proof of the Optimality of the Shortest Remaining Processing Time Discipline [pp. 197 - 199]Improved Dominance Conditions for the Three-Machine Flowshop Scheduling Problem [pp. 200 - 203]Dominance Conditions for the Three-Machine Flow-Shop Problem [pp. 203 - 206]Three-Stage Flow-Shops with Recessive Second Stage [pp. 207 - 208]Back Matter