Improved Approximation Schemes for Scheduling Unrelated Parallel Machines

References

• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows (1993) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Amoura A. K., Bampis E., Kenyon C., Manoussakis Y. Scheduling independent multiprocessor tasks. Proc. 5th Ann. Eur. Sympos. Algorithms (1997) 1–12LNCS 1284Crossref, Google Scholar
• Grigoriadis M. D., Khachiyan L. G. Coordination complexity of parallel price-directive decomposition. Math. Oper. Res. (1996) 21:321–340Link, Google Scholar
• Horowitz E., Sahni S. Exact and approximate algorithms for scheduling nonidentical processors. J. Assoc. Comput. Machinery (1976) 23:317–327Crossref, Google Scholar
• Jansen K. L., Porkolab. Linear-time approximation schemes for scheduling malleable parallel tasks. Proc. 10th Ann. ACM-SIAM Sympos. Discrete Algorithms (1999a) 490–498Google Scholar
• Jansen K. L., Porkolab. General multiprocessor task scheduling: approximate solution in linear time. Proc. 6th Internat. Workshop Algorithms Data Structures (1999b) (Springer Verlag)110–121LNCS 1663Crossref, Google Scholar
• Jansen K. L., Solis-Oba R., Sviridenko M. I. A linear time approximation scheme for the job shop scheduling problem. Proc. 2nd Workshop on Approximation Algorithms (1999) (Springer Verlag)177–188LNCS 1671Crossref, Google Scholar
• Kopidakis Y., Fayard D., Zissimopoulos V. Linear time approximation schemes for parallel processor scheduling. Proc. 8th IEEE Sympos. Parallel Distributed Processing (1996) 482–485Crossref, Google Scholar
• Lawler E. L., Labetoulle J. On preemptive scheduling of unrelated parallel processors by linear programming. J. Assoc. Comput. Machinery (1978) 25:612–619Crossref, Google Scholar
• Lenstra J. K., Shmoys D. B., Tardos E. Approximation algorithms for scheduling unrelated parallel machines. Math. Programming (1990) 46:259–271Crossref, Google Scholar
• Lin J.-H., Vitter J. S. ε-approximations with minimum packing constraint violation. Proc. 24th ACM Sympos. Theory Comput. (1992) 771–782Google Scholar
• Plotkin S. A., Shmoys D. B., Tardos E. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. (1995) 20:257–301Link, Google Scholar
• Shmoys D. B., Tardos E. An approximation algorithm for the generalized assignment problem. Math. Programming (1993) 62:461–474Crossref, Google Scholar
• Trick M. A. Scheduling multiple variable-speed machines. Proc. 1st Integer Programming Combinatorial Optim. Conf. (1990) 485–494Google Scholar
• Villavicencio J., Grigoriadis M. D., Fischer H., et al. Approximate structured optimization by cyclic block-coordinate descent. Applied Mathematics and Parallel Computing—Festschrift for Klaus Ritter (1996) (Physica-Verlag, Heidelberg, Germany) Crossref, Google Scholar