Asymptotic optimality of shortest processing time-based algorithms for flow shop and open shop problems with nonlinear objective functions

References

• Bai, D., and T. Ren. 2013. “New Approximation Algorithms for Flow Shop Total Completion Time Problem.” Engineering Optimization 45: 1091–1105. doi: 10.1080/0305215X.2012.720680
   Web of Science ®Google Scholar
• Bai, D., and L. Tang. 2007. “Worst Case Analysis of a New Lower Bound for Flow Shop Weighted Completion Time Problem.” Lecture Notes in Computer Science 4616: 191–199. doi: 10.1007/978-3-540-73556-4_22
   Google Scholar
• Bai, D., and L. Tang. 2011. “Performance Analysis of Rotation Schedule and Improved Strategy for Open Shop Problem to Minimize Makespan.” International Journal of Systems Science 42: 1143–1153. doi: 10.1080/00207720903308397
   Web of Science ®Google Scholar
• Bai, D., and Z. Zhang. 2012. “On the Asymptotic Optimality and Improved Strategies of SPTB Heuristic for Open Shop Scheduling Problem.” International Journal of Systems Science [online]. http://dx.doi.org/10.1080/00207721.2012.748943
   Google Scholar
• Brucker, P. 2004. Scheduling Algorithms. 4th ed. Berlin: Springer.
   Google Scholar
• Chen, B., C. N. Potts, and G. J. Woeginger. 1998. “A Review of Machine Scheduling: Complexity, Algorithms and Approximability.” In Handbook of Combinatorial Optimization, edited by D.-Z. Du and P. Pardalos, 21–169. London: Kluwer Academic Publishers.
   Google Scholar
• Cheng, T. C. E., and Z. Liu. 2004. “Parallel Machine Scheduling to Minimize the Sum of Quadratic Completion Times.” IIE Transactions 36: 11–17. doi: 10.1080/07408170490257844
   Web of Science ®Google Scholar
• Della Croce, F., and C. Koulamas. 2012. “A Note on Minimizing the Sum of Quadratic Completion Times on Two Identical Parallel Machines.” Information Processing Letters 112: 738–742. doi: 10.1016/j.ipl.2012.06.011
   Web of Science ®Google Scholar
• Graham, R. L., E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. 1979. “Optimization and Approximation in Deterministic Machine Sequencing and Scheduling: A Survey.” Annual Discrete Mathematics 5: 287–326. doi: 10.1016/S0167-5060(08)70356-X
   Google Scholar
• Janiak, A., T. Krysiak, C. Pappis, and T. Voutsinas. 2009. “A Scheduling Problem with Job Values Given as a Power Function of Their Completion Times.” European Journal of Operational Research 193: 836–848. doi: 10.1016/j.ejor.2007.11.006
   Web of Science ®Google Scholar
• Johnson, S. M. 1954. “Optimal Two- and Three-Stage Production Schedules with Setup Times Included.” Naval Research Logistics 1: 61–68. doi: 10.1002/nav.3800010110
   Google Scholar
• Kaminsky, P., and D. Simchi-Levi. 2001a. “The Asymptotic Optimality of the SPT Rule for the Flow Shop Mean Completion Time Problem.” Operations Research 49: 293–304. doi: 10.1287/opre.49.2.293.13536
   Web of Science ®Google Scholar
• Kaminsky, P., and D. Simchi-Levi. 2001b. “Asymptotic Analysis of an On-Line Algorithm for the Single Machine Completion Time Problem with Release Dates.” Operations Research Letters 29: 141–148. doi: 10.1016/S0167-6377(01)00099-2
   Web of Science ®Google Scholar
• Koulamas, C., and G. Kyparisis. 2005. “Algorithms with Performance Guarantees for Flow Shops with Regular Objective Functions.” IIE Transactions 37: 1107–1111. doi: 10.1080/07408170500288067
   Web of Science ®Google Scholar
• Lenstra, J. K., A. H. G. Rinnooy Kan, and P. Brucker. 1977. “Complexity of Machine Scheduling Problems.” Annual Discrete Mathematics 1: 343–362. doi: 10.1016/S0167-5060(08)70743-X
   Google Scholar
• Liu, H., M. Queyranne, and D. Simchi-Levi. 2005. “On the Asymptotic Optimality of Algorithms for the Flow Shop Problem with Release Dates.” Naval Research Logistics 52: 232–242. doi: 10.1002/nav.20066
   Web of Science ®Google Scholar
• Schrage, L. 1968. “A Proof of the Optimality of the Shortest Remaining Processing Time Discipline.” Operations Research 16: 687–690. doi: 10.1287/opre.16.3.687
   Web of Science ®Google Scholar
• Tang, L., and D. Bai. 2010. “A New Heuristic for Open Shop Total Completion Time Problem.” Applied Mathematical Modelling 34: 735–743. doi: 10.1016/j.apm.2009.06.014
   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. doi: 10.1287/mnsc.24.5.530
   Web of Science ®Google Scholar
• Wang, J.-B., and M.-Z. Wang. 2012. “Worst-Case Analysis for Flow Shop Scheduling Problems with an Exponential Learning Effect.” Journal of the Operational Research Society 63: 130–137. doi: 10.1057/jors.2011.40
   Web of Science ®Google Scholar
• Xia, C. H., J. G. Shanthikumar, and P. W. Glynn. 2000. “On the Asymptotic Optimality of the SPT Rule for the Flow Shop Average Completion Time Problem.” Operations Research 48: 615–622. doi: 10.1287/opre.48.4.615.12423
   Web of Science ®Google Scholar
• Xu, Z., L. Sun, and J. Gong. 2008. “Worst-Case Analysis for Flow Shop Scheduling with a Learning Effect.” International Journal of Production Economics 113: 748–753. doi: 10.1016/j.ijpe.2007.11.002
   Web of Science ®Google Scholar