Algorithms with performance guarantees for flow shops with regular objective functions

References

• Cheng , T. C.E. and Liu , Z. 2004 . Parallel machine scheduling to minimize the sum of quadratic completion times . IIE Transactions , 36 : 11 – 17 .
   Web of Science ®Google Scholar
• Garey , M. R. , Johnson , D. S. and Sethi , R. 1976 . The complexity of flowshop and jobshop scheduling . Mathematics of Operations Research , 1 : 117 – 129 .
   Google Scholar
• Glynn , P. W. and Whitt , W. 1991 . Departures from many queues in series . Annals of Applied Probability , 1 : 546 – 572 .
   Google Scholar
• Gonzalez , T. 1979 . NP-hard shop problems , Technical report CS-79-35 USA : Department of Computer Science, The Pennsylvania State University, University Park, PA 16803 .
   Google Scholar
• Gonzalez , T. 1982 . Unit execution time shop problems . Mathematics of Operations Research , 7 : 57 – 66 .
   Web of Science ®Google Scholar
• Gonzalez , T. and Sahni , S. 1978 . Flowshop and jobshop schedules: complexity and approximation . Operations Research , 26 : 36 – 52 .
   Web of Science ®Google Scholar
• Gordon , V. S. and Shafransky , Y. M. 1978a . Optimal ordering with series-parallel precedence constraints . Doklady Akademii Nauk BSSR (Proceedings of the Academy of Sciences of the BSSR , 22 ( 3 ) : 244 – 247 . in Russian
   Web of Science ®Google Scholar
• Gordon , V. S. and Shafransky , Y. M. 1978b . On optimal ordering with series-parallel precedence constraints . Vestsi Akademii Nauk BSSR Ser. Fizika-matematychnyh Nauk Transactions of the Academy of Sciences of the BSSR Phys.-Math Series , 22 ( 5 ) : 135 in Russian
   Google Scholar
• Gordon , V. S. and Tanaev , V. S. 1973 . “ Single-machine deterministic scheduling with treelike ordered jobs and exponential penalty functions ” . In Computers in Engineering , 3 – 10 . Minsk . in Russian
   Google Scholar
• Gupta , S. K. , Kyparisis , J. and Ip , C. -M. 1992 . Project selection and sequencing to maximize net present value of the total return . Management Science , 38 : 751 – 752 .
   Web of Science ®Google Scholar
• Johnson , S. M. 1954 . Optimal two- and three-stage production schedules with setup times included . Naval Research Logistics Quarterly , 1 : 61 – 68 .
   Google Scholar
• Kaminsky , P. and Simchi-Levi , D. 2001 . The asymptotic optimality of the SPT rule for the flow shop mean completion time problem . Operations Research , 49 : 293 – 304 . [CROSSREF]
   Web of Science ®Google Scholar
• Lawler , E. L. 1973 . Optimal sequencing of a single machine subject to precedence constraints . Management Science , 19 : 544 – 546 .
   Web of Science ®Google Scholar
• Lawler , E. L. 1978 . Sequencing jobs to minimize total weighted completion time subject to precedence constraints . Annals of Discrete Mathematics , 2 : 75 – 90 .
   Google Scholar
• Lawler , E. L. , Lenstra , J. K. , Rinnooy Kan , A. H.G. and Shmoys , D. B. 1993 . “ Sequencing and scheduling: algorithms and complexity ” . In Handbooks in Operations Research and Management Science, Volume 4: Logistics of Production and Inventory , Edited by: Graves , S. C. , Rinnooy Kan , A. H.G. and Zipkin , P. M. 445 – 522 . Amsterdam, The Netherlands : North-Holland .
   Google Scholar
• Lawler , E. L. and Sivazlian , B. D. 1978 . Minimization of time-varying costs in single-machine scheduling . Operations Research , 26 : 563 – 569 .
   Web of Science ®Google Scholar
• Lenstra , J. K. , Rinnoy Kan , A. H.G. and Brucker , P. 1977 . Complexity of machine scheduling problems . Annals of Discrete Mathematics , 1 : 343 – 362 .
   Google Scholar
• Monma , C. L. 1979 . The two-machine maximum flow-time problem with series-parallel precedence constraints: an algorithm and extensions . Operations Research , 27 : 792 – 798 .
   Web of Science ®Google Scholar
• Monma , C. L. 1980 . Sequencing to minimize the maximum job cost . Operations Research , 28 : 942 – 951 .
   Web of Science ®Google Scholar
• Pinedo , M. 2002 . Scheduling: Theory, Algorithms, and Systems , Upper Saddle River, New Jersey : Prentice Hall . 07458
   Google Scholar
• Rothkopf , M. H. 1966 . Scheduling independent tasks on parallel processors . Management Science , 12 : 437 – 447 .
   Google Scholar
• Rothkopf , M. H. and Smith , S. S. 1984 . There are no undiscovered priority index sequencing rules for minimizing total delay costs . Operations Research , 32 : 451 – 456 .
   Web of Science ®Google Scholar
• Sidney , J. B. 1979 . The two-machine maximum flow time problem with series parallel precedence relations . Operations Research , 27 : 782 – 791 .
   Web of Science ®Google Scholar
• Smith , W. E. 1956 . Various optimizers for single-stage production . Naval Research Logistics Quarterly , 3 : 54 – 66 .
   Google Scholar
• Smutnicki , C. 1998 . Some results of the worst-case analysis for flow shop scheduling . European Journal of Operational Research , 109 : 66 – 87 . [CROSSREF]
   Web of Science ®Google Scholar
• Townsend , W. 1978 . The single machine problem with quadratic penalty function of completion times: a branch-and-bound solution . Management Science , 24 : 530 – 534 .
   Web of Science ®Google Scholar
• Xia , C. H. , Shanthikumar , J. G. and Glynn , P. W. 2000 . On the asymptotic optimality of the spt rule for the flow shop average completion time problem . Operations Research , 4 : 615 – 622 . [CROSSREF]
   Web of Science ®Google Scholar