A parametric worst case analysis of the LPT heuristic for two uniform machines
Mireault, P.; Orlin, J.B.; Vohra, R.V.
Operations Research 45(1): 116-125
1997
ISSN/ISBN: 0030-364X Accession: 073761195
PDF emailed within 1 workday: $29.90
Related References
Li, K; Yang, S 2011: Heuristic algorithms for scheduling on uniform parallel machines with heads and tails Journal of Systems Engineering and Electronics 22(3): 462-467Skelin, M.; Geilen, M.; Catthoor, F.; Hendseth, S. 2014: Worst-case Throughput Analysis for Parametric Rate and Parametric Actor Execution time Scenario-Aware Dataflow Graphs Electronic Proceedings in Theoretical Computer Science 145: 65-79
Senthilkumar, P.; Narayanan, S. 2011: GA Based Heuristic to Minimize Makespan in Single Machine Scheduling Problem with Uniform Parallel Machines Intelligent Information Management 03(05): 204-214
Erkiö, H. 1980: A heuristic approximation of the worst case of Shellsort BIT 20(2): 130-136
Fisher, M.L. 1980: Worst-Case Analysis of Heuristic Algorithms Management Science 26(1): 1-17
Kaihong, X.U. 2000: The asymptotic worst-case behavior of the FFD heuristic for small items Journal of Algorithms 37(2): 237-246
Candiavejar, A.; Bravoazlan, H. 2006: Worst-case performance of Wong's Steiner tree heuristic Discrete Appl. Math 154(5): 730-737
Soper, A.J.; Strusevich, V.A. 2018: Parametric analysis of the quality of single preemption schedules on three uniform parallel machines Annals of Operations Research 298(1-2): 469-495
Ramezani, P.; Rabiee, M.; Jolai, F. 2013: No-wait flexible flowshop with uniform parallel machines and sequence-dependent setup time: a hybrid meta-heuristic approach Journal of Intelligent Manufacturing 26(4): 731-744
Waxman, B.M.; Imase, M. 1988: Worst-case performance of Rayward-Smith's Steiner tree heuristic Information Processing Letters 29(6): 283-287
Averbakh, I.; Berman, O. 1996: A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree Discrete Applied Mathematics 68(1-2): 17-32
Insoo, L.E.E. 1991: A worst-case performance of the shortest-processing-time heuristic for single machine scheduling The Journal of the Operational Research Society 42(10): 895-901
Balakrishnan, A.; Magnanti, T.L.; Mirchandani, P. 1994: Modeling and Heuristic Worst-Case Performance Analysis of the Two-Level Network Design Problem Management Science 40(7): 846-867
Bertsimas, D.; Grigni, M. 1989: Worst-case examples for the spacefilling curve heuristic for the Euclidean Traveling Salesman Problem Operations Research Letters 8(5): 241-244
Poljak, S.; Turzik, D. 1986: A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound Discrete Mathematics 58(1): 99-104
Yupei, X.I.O.N.G.; Golden, B.; Wasil, E. 2005: Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem Operations Research Letters 33(1): 77-80
Imahori, S.; Yagiura, M. 2010: The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio Computers and Operations Research 37(2): 325-333
Lam, H.; Mottet, C. 2017: Tail Analysis Without Parametric Models: a Worst-Case Perspective Operations Research 65(6): 1696-1711
Chen, B.; Strusevich, V.A. 1993: Worst-case analysis of heuristics for open shops with parallel machines European Journal of Operational Research 70(3): 379-390
Kacem, I.; Chu, C. 2008: Minimizing the weighted flow time on a single machine with the resumable availability constraint: worst case of the WSPT heuristic International Journal of Computer Integrated Manufacturing 21(4): 388-395