The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders

References

• Afrati F., Bampis E., Chekuri C., Karger D., Kenyon C., Khanna S., Milis I., Queyranne M., Skutella M., Stein C., Sviridenko M. Approximation schemes for minimizing average weighted completion time with release dates. Proc. 40th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (1999) (IEEE Computer Society, Washington, DC) 32–43Crossref, Google Scholar
• Ambühl C., Mastrolilli M. Single machine precedence constrained scheduling is a vertex cover problem. Algorithmica (2009) 53:488–503Crossref, Google Scholar
• Ambühl C., Mastrolilli M., Svensson O. Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut. SIAM J. Comput. (2011) 40:567–596Crossref, Google Scholar
• Bansal N., Khot S. Optimal long code test with one free bit. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (2009) (IEEE Computer Society, Washington, DC) 453–462Crossref, Google Scholar
• Bansal N., Khot S. Inapproximability of hypergraph vertex cover and applications to scheduling problems. Proc. 37th Internat. Colloquium on Automata, Languages and Programming (ICALP) (2010) 6198(Springer-Verlag, Berlin) 250–261Lecture Notes in Computer ScienceCrossref, Google Scholar
• Canetti R., Irani S. Bounding the power of preemption in randomized scheduling. SIAM J. Comput. (1998) 27:993–1015Crossref, Google Scholar
• Chekuri C., Motwani R. Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Appl. Math. (1999) 98:29–38Crossref, Google Scholar
• Chen Z., Hall N. G. Supply chain scheduling: Assembly systems. (2001) . Technical report, Ohio State University, ColumbusGoogle Scholar
• Chen Z., Hall N. G. Supply chain scheduling: Conflict and cooperation in assembly systems. Oper. Res. (2007) 55:1072–1089Link, Google Scholar
• Chudak F., Hochbaum D. S. A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Oper. Res. Lett. (1999) 25:199–204Crossref, Google Scholar
• Correa J. R., Schulz A. S. Single machine scheduling with precedence constraints. Math. Oper. Res. (2005) 30:1005–1021Link, Google Scholar
• Correa J. R., Skutella M., Verschae J.Proc. 12th Internat. Workshop and 13th Internat. Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM) (2009) 5687(Springer-Verlag, Berlin)84–97Lecture Notes in Computer ScienceCrossref, Google Scholar
• Dyer M. E., Wolsey L. A. Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math. (1999) 26:255–270Crossref, Google Scholar
• Eastman W. L., Even S., Isaacs I. M. Bounds for the optimal scheduling of n jobs on m processors. Management Sci. (1964) 11:268–279Link, Google Scholar
• Graham R. L. Bounds for certain multiprocessing anomalies. AT&T Tech. J. (1966) 45:1563–1581Google Scholar
• Hall L. A., Schulz A. S., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. (1997) 22:513–544Link, Google Scholar
• Hochbaum D., Shmoys D. B. Using dual approximation algorithms for scheduling problems: Theoretical and practical results. J. ACM (1987) 34:144–162Crossref, Google Scholar
• Hoogeveen H., Schuurman P., Woeginger G. J. Nonapproximability results for scheduling problems with minsum criteria. INFORMS J. Comput. (2001) 13:157–168Link, Google Scholar
• Khot S. On the power of unique 2-prover 1-round games. Proc. 34th Annual ACM Sympos. Theory Comput. (STOC) (2002) (ACM, New York) 767–775Crossref, Google Scholar
• Lawler E. L., Labetoulle J. On preemptive scheduling of unrelated parallel processors by linear programming. J. ACM (1978) 25:612–619Crossref, Google Scholar
• Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B., Graves S. C., Rinnooy Kan A. H. G., Zipkin P. H. Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science (1993) 4(North-Holland, Amsterdam) 445–522Logistics of Production and InventoryGoogle Scholar
• Lenstra J. K., Rinnooy Kan A. H. G. Complexity of scheduling under precedence constraints. Oper. Res. (1978) 26:22–35Link, Google Scholar
• Lenstra J. K., Shmoys D. B., Tardos É. Approximation algorithms for scheduling unrelated parallel machines. Math. Programming (1990) 46:259–271Crossref, Google Scholar
• Leung J., Li H., Pinedo M. Approximation algorithm for minimizing total weighted completion time of orders on identical parallel machines. Naval. Res. Logist. (2006) 53:243–260Crossref, Google Scholar
• Leung J., Li H., Pinedo M. Scheduling orders for multiple product types to minimize total weighted completion time. Discrete Appl. Math. (2007) 155:945–970Crossref, Google Scholar
• Leung J., Li H., Pinedo M., Zhang J. Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines. Inform. Processing Lett. (2007) 103:119–129Crossref, Google Scholar
• Lin J.-H., Vitter J. S. ε-approximations with minimum packing constraint violation. Proc. 24th Annual ACM Sympos. Theory of Comput. (STOC) (1992) (ACM, New York) 771–782Google Scholar
• Margot F., Queyranne M., Wang Y. Decompositions, network flows, and a precedence constrained single machine scheduling problem. Oper. Res. (2003) 51:981–992Link, Google Scholar
• Mastrolilli M., Queyranne M., Schulz A. S., Svensson O., Uhan N. A. Minimizing the weighted sum of completion times in concurrent open shops. Oper. Res. Lett. (2010) 38:390–395Crossref, Google Scholar
• Queyranne M. Structure of a simple scheduling polyhedron. Math. Programming (1993) 58:263–285Crossref, Google Scholar
• Schulz A. S., Skutella M. Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math. (2002) 15:450–469Crossref, Google Scholar
• Shachnai H., Tamir T. Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica (2002) 32:651–678Crossref, Google Scholar
• Shmoys D. B., Tardos É. An approximation algorithm for the generalized assignment problem. Math. Programming (1993) 62:461–474Crossref, Google Scholar
• Skutella M. Convex quadratic and semidefinite programming relaxations in scheduling. J. ACM (2001) 48:206–242Crossref, Google Scholar
• Skutella M., Woeginger G. J. Minimizing the total weighted completion time on identical parallel machines. Math. Oper. Res. (2000) 25:63–75Link, Google Scholar
• Smith W. E. Various optimizers for single-stage production. Naval Res. Logist. Quart. (1956) 3:59–66Crossref, Google Scholar
• Verschae J. Approximation algorithms for scheduling orders on parallel machines. (2008) . Mathematical engineering thesis, Universidad de Chile, Santiago, ChileGoogle Scholar
• Woeginger G. J. On the approximability of average completion time scheduling under precedence constraints. Discrete Appl. Math. (2003) 131:237–252Crossref, Google Scholar
• Yang J., Posner M. E. Scheduling parallel machines for the customer order problem. J. Sched. (2005) 8:49–74Crossref, Google Scholar