Advanced search
Publication Cover
Production Planning & Control
The Management of Operations
Volume 13, 2002 - Issue 2
Submit an article Journal homepage
238
Views
92
CrossRef citations to date
0
Altmetric
Original Articles

Due date assignment and scheduling: Slk, TWK and other due date assignment models

Valery S. Gordon
,
Jean-Marie Proth
&
Chengbin Chu
Pages 117-132 | Published online: 15 Nov 2010

  • ADAMOPOULOS , G. I. and PAPPB , C. P. 1996a . Scheduling with different, job-dependent earliness and tardiness penalties using SLK method . European Journal of Operational Research , 88 : 336 – 344 .
  • ADAMOPOULOS , G. I. and PAPPK , C. P. 1996b . Single machine scheduling with flow allowances . Journal of the Operational Research Society , 47 : 1280 – 1285 .
  • AGNETS , A. , MACCHIAROLI , R. , PACCIARELLI , D. and ROSSL , F. 1997 . Assigning jobs to time frames on a single machine to minimize total tardiness . HE Transactions , 29 : 965 – 976 .
  • ALIDAEE , B. 1991 . Optimal assignment of slack due-dates and sequencing in a single machine shop . Applied Mathematics Letters , 4 : 9 – 11 .
  • ALIDAEE , B. 1992 . Optimal assignment of NOP due-dates and sequencing in a single machine shop . ZOR-Mathematical Methods of Operations Research , 36 : 333 – 341 .
  • BAKER , K. R. and SCUDDER , G. D. 1990 . Sequencing with earliness and tardiness penalties: a review . Operations Research , 38 : 22 – 36 .
  • BAKER , K. R. , LAWLER , E. L. , LENSTRA , J. K. and RINNOOY KAN , A. H. G. 1983 . Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints . Operations Research , 31 : 381 – 386 .
  • BLAZEWICZ , J. 1976 . “ Scheduling dependent tasks with different arrival times to meet deadlines ” . In Modelling and Performance Evaluation of Computer Systems , Edited by: Gelenbe , E. and Beilner , H. 57 – 65 . Amsterdam : Elscvicr Science .
  • CHAND , S. and CHHAJED , D. 1992 . A single machine model for determination of optimal due dates and sequence . Operations Research , 40 : 596 – 602 .
  • CHEN , B. , POTTS , C. N. and WOEGINGER , G. J. 1998 . “ A review of machine scheduling: complexity, algorithms and approximability ” . In Handbook of Combinatorial Optimization , Edited by: Du , D.-Z. and Pardalos , P. M. 21 – 169 . Dordrecht : Kluwcr .
  • CHENG , T. C. E. 1984 . Optimal due-date determination and sequencing of n jobs on a single machine . Journal of the Operational Research Society , 35 : 433 – 437 .
  • CHENG , T. C. E. 1987a . Optimal TWK-powcr due-date determination and sequencing . International Journal of System Sciences , 18 : 1 – 7 .
  • CHENG , T. C. E. 1987b . Optimal total-work-contcnt-powcr due-date determination and sequencing . Computers and Mathematics with Applications , 14 : 579 – 582 .
  • CHENG , T. C. E. 1989 . Optimal assignment of slack due-dates and sequencing in a single-machine shop . Applied Mathematics Letters , 2 : 333 – 335 .
  • CHENG , T. C. E. 1991 . Optimal assignment of total-work-constant-duc-datcs and sequencing in a single machine shop . Journal of the Operational Research Society , 42 : 177 – 181 .
  • CHENG , T. C. E. and GUPTA , M. C. 1989 . Survey of scheduling research involving due date determination decisions . European Journal of Operational Research , 38 : 156 – 166 .
  • CHENG , T. C. E. and Li , S. 1989 . Some observations and extensions of the optimal TWK-powcr due-date determination and sequencing problem . Computers and Mathematics with Applications , 17 : 1103 – 1107 .
  • CHENG , T. C. E. and GORDON , V. S. 1994 . Optimal assignment of due-dates for preemptive single-machine scheduling . Mathematical and Computer Modelling , 20 : 33 – 40 .
  • CHENG , T. C. E. and JIANG , J. 1998 . Job shop scheduling with missed due-date performance . Computers and Industrial Engineering , 34 : 297 – 307 .
  • CHENG , T. C. E. and KOVALYOV , M. Y. 1999 . Complexity of parallel machine scheduling with proccssing-plus-wait due dates to minimize maximum absolute lateness . European Journal of Operational Research , 114 : 403 – 410 .
  • CHO , Y. and SAHNI , S. 1981 . Preemptive scheduling of independent jobs with release and due times on open, flow and job shops . Operations Research , 29 : 511 – 522 .
  • CHU , C. 1996 . A new class of scheduling criteria and their optimization . RAIRO Recherche operationnelle , 30 : 171 – 189 .
  • CHU , C. and GORDON , V. TWK due date determination and scheduling model: NP-hardnes and polynomially solvable case. Discrete Optimization Methods in Scheduling and ComputerAided Design . Proceedings of the International Workshop . Minsk. pp. 21 – 25 . National Academy of Sciences of Belarus .
  • DE , P. , GHOSH , J. B. and WELLS , C. E. 1992 . On the minimization of completion time variance with a bicriteria extension . Operations Research , 40 : 1148 – 1155 .
  • Du , J. and LEUNG , J. Y.-T. 1990 . Minimizing total tardiness on one machine is N P-hard . Mathematics of Operations Research , 15 : 483 – 495 .
  • GAREY , M. R. , TARJAN , R. E. and WILFONG , G. T. 1988 . One-processor scheduling with symmetric earliness and tardiness penalties . Mathematics of Operations Research , 13 : 330 – 348 .
  • GONZALEZ , T. and JOHNSON , D.B. 1980 . A new algorithm for preemptive scheduling of trees . Journal of the Association for Computing Machinery , 27 : 287 – 312 .
  • GORDON , V. S. and TANAEV , V. S. 1983 . On minmax single machine scheduling problems , Ser. Fiz.-Mat. Nauk, 3 3 – 9 . Izuestiya Akademn Nauk BSSR . (In Russian)
  • GORDON , V. S. 1993 . A note on optimal assignment of slack due-dates in single-machine scheduling . European Journal of Operational Research , 70 : 311 – 315 .
  • GORDON , V. S. and KUBIAK , W. 1996 . “ Minimizing the weighted number of late jobs with release and due date assignment ” . In Industrial Scheduling of Robots and Flexible Manufacturing Systems , Edited by: Lcvncr , E. 127 – 130 . Holon : CTEH Press .
  • GORDON , V. S. and KUBIAK , W. 1999 . Single machine scheduling with release and due date assignment to minimize the weighted number of late jobs . Information Processing Letters , 68 : 153 – 159 .
  • GORDON , V. S. and STRUSEVICH , V. A. 1999 . Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment . Computers and Operations Research , 26 : 157 – 177 .
  • GORDON , V. S. , PROTH , J.-M. and CHU , C. 1998 . A state-ofthe-art survey of due date assignment and scheduling research: common due date , Research Report RR-3454 1 – 28 . France : INRIA .
  • GORDON , V. S. , PROTH , J.-M. and CHU , C. 2001 . A survey of the state-of-the-art of common due date assignment and scheduling research . European Journal of Operational Research , (to appear)
  • GUPTA , S. K. and SEN , T. 1983 . Minimizing a quadratic function of job lateness on a single machine . Engineering Costs and Production Economics , 7 : 187 – 194 .
  • GUPTA , Y. P. , SECTOR , C. R. and GUPTA , M. C. 1990 . Optimal schedule on a single machine using various due date determination methods . Computers in Industry , 15 : 245 – 253 .
  • HALL , N. G. 1986 . Scheduling problems with generalized due dates . HE Transactions , 18 : 220 – 222 .
  • HALL , N. G. , KUBIAK , W. and SETHI , S. P. 1991a . Earlinesstardincss scheduling problems, II: Deviation of completion times about a restrictive common due date . Operations Research , 39 : 847 – 856 .
  • HALL , N. G. , SETHI , S. P. and SRISKANDARAJAH , C. 1991b . On the complexity of generalized due date scheduling problems . European Journal of Operational Research , 51 : 100 – 109 .
  • HIMMELBLAU , D. M. 1972 . Applied Nonlinear Programming , New York : McGraw-Hill .
  • HOOGEVEEN , J. A. and VANDEVELDE , S. L. 1991 . Scheduling around a small common due date . European Journal of Operational Research , 55 : 237 – 242 .
  • HOOGEVEN , J. A. , LENSTRA , J. K. and VAN DE VELDE , S. L. 1997 . Sequencing and scheduling: an annotated bibliography , Memorandum COSOR 97-02 1 – 17 . Eindhoven University of Technology .
  • HORN , W. A. 1974 . Some simple scheduling algorithms . Nasal Research Logistics Quarterly , 21 : 177 – 185 .
  • KAHLBACHER , H. G. 1989 . A program for a scheduling problem with earliness and tardiness penalties . European Journal of Operational Research , 43 : 111 – 112 .
  • KAHLBACHER , H. G. 1993 . Scheduling with monotonous carlincss and tardiness penalties . European Journal of Operational Research , 64 : 258 – 277 .
  • KAHLBACHER , H. G. and CHENG , T. C. E. 1995 . Processingplus-wait due dates in single-machine scheduling . Journal of Optimization Theory and Applications , 85 : 163 – 186 .
  • KARACAPILIDIS , N. I. and PAPPIS , C. P. 1993 . Optimal duedate determination and sequencing of n jobs on a single machine using the SLK method . Computers in Industry , 21 : 335 – 339 .
  • KARACAPILIDIS , N. I. and PAPPIS , C. P. 1995 . Form similarities of the CON and SLK due date determination methods . Journal of the Operational Research Society , 46 : 762 – 770 .
  • KUBIAK , W. 1993 . Completion time variance minimization on a single machine is difficult . Operations Research Letters , 14 : 49 – 59 .
  • LAWLER , E. L. 1973 . Optimal sequencing of a single machine subject to precedence constraints . Management Science , 19 : 544 – 546 .
  • LAWLER , E. L. 1977 . A 'pscudopolynomial' algorithm for sequencing jobs to minimize total tardiness . Annals of Discrete Mathematics , 1 : 331 – 342 .
  • LAWLER , E. L. , LENSTRA , J. K. , RINNOOYKAN , A. H. G. and SHMOYS , D. B. 1993 . “ Sequencing and scheduling: algorithms and complexity ” . In Logistics of Production and Inventory; Handbooks in Operations Research and Management Science , Edited by: Graves , S. C. , Zipkin , P. H. and Rinnooy Kan , A. H. G. Vol. 4 , 445 – 522 . Amsterdam : Elscvicr Science .
  • LEE , I.-S. 1991 . A worst-case performance of the shortcst-proccssing-timc hcuristk for single machine scheduling . Journal of the Operational Research Society , 42 : 895 – 901 .
  • LENSTRA , J. K. and RINNOOY KAN , A. H. G. 1980 . Complexity results for scheduling chains on a single machine . European Journal of Operational Research , 4 : 270 – 275 .
  • LENSTRA , J. K. , RINNOOY KAN , A. H. G. and BRUCKER , P. 1977 . Complexity of machine scheduling problems . Annals of Discrete Mathematics , 1 : 343 – 362 .
  • LEUNG , J. Y.-T. and YOUNG , G. H. 1989 . Minimizing total tardiness on a single machine with precedence constraints , Dallas : Computer Science Program. Univ. of Texas . Technical report
  • MOORE , J. M. 1968 . An n job, one machine sequencing algorithm for minimizing the number of late jobs . Management Science , 15 : 102 – 109 .
  • MUTLU , O. 1993 . Comments on optimal due-date determination and sequencing of n jobs on a single machine . Journal of the Operational Research Society , 44 : 1062
  • OGUZ , C. and DINCER , C. 1994 . Single machine carlincss-tardiness scheduling problems using the equal-slack rule . Journal of the Operational Research Society , 45 : 589 – 594 .
  • PANWALKAR , S. S. , SMITH , M. L. and SEIDMANN , A. 1982 . Common due date assignment to minimize total penalty for the one machine scheduling problem . Operations Research , 30 : 391 – 399 .
  • PAPPIS , C. P. and ADAMOPOULOS , G. I. 1993 . Scheduling under the due date criterion with varying penalties for lateness . Yugoslavian Journal of Operations Research , 3 : 189 – 198 .
  • POLAK , E. 1997 . Optimization. Algorithms and Consistent Approximations , New York : Springer .
  • Qi , X. and Tu , F. S. 1998 . Scheduling a single machine to minimize carlincss penalties subject to SLK due-date determination method . European Journal of Operational Research , 105 : 502 – 508 .
  • SEIDMANN , A. , PANWALKAR , S. S. and SMITH , M. L. 1981 . Optimal assignment of due-dates for a single processor scheduling problem . International Journal of Production Research , 19 : 393 – 399 .
  • SRISKANDARAJAH , C. 1990 . A note on the generalized due date scheduling problems . Naval Research Logistics , 37 : 587 – 597 .
  • SZWARC , W. 1990 . Parametric precedence relations in single machine scheduling . Operations Research Letters , 9 : 133 – 140 .
  • TANAEV , V. S. , GORDON , V. S. and SHAFRANSKY , Y. M. 1994 . Scheduling Theory: Single-Stage Systems , Dordrecht : Kluwcr .
  • TANAKA , K. and VLACH , M. 1997a . Single machine scheduling to minimize the maximum lateness with both specific and generalized due dates . IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , : 557 – 583 . E80-A
  • TANAKA , K. and VLACH , M. 1997b . Minimizing the range of lateness on a single machine under generalized due dates . Information Systems and Operational Research , 35 : 286 – 296 .
  • VALDES , J. R. , TARJAN , R. E. and LAWLER , E. L. 1982 . The recognition of series-parallel digraphs . SIAM Journal on Computing , 11 : 361 – 370 .
  • VAN DE VELDE , S. L. 1990 . A simpler and faster algorithm for optimal total-work-contcnt-powcr due date determination . Mathematical and Computer Modelling , 13 : 81 – 83 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.