Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines

References

• Ahuja RK, Orlin JB, Stein C, Tarjan RE (1994) Improved algorithms for bipartite network flow. SIAM J. Comput. 23:906–933.Crossref, Google Scholar
• Bansal N, Pruhs K, Stein C (2009) Speed scaling for weighted flow time. SIAM J. Comput. 39:1294–1308.Crossref, Google Scholar
• Bunde DP (2009) Power-aware scheduling for makespan and flow. J. Sched. 12:489–500.Crossref, Google Scholar
• Chung JY, Shih W-K, Liu JWS, Gillies DW (1989) Scheduling imprecise computations to minimize total error. Microproc. Microprogram. 27:767–774.Crossref, Google Scholar
• Federgruen A, Groenevelt H (1986) Preemptive scheduling of uniform machines by ordinary network flow techniques. Management Sci. 32:341–349.Link, Google Scholar
• Fujishige S (2005) Submodular Functions and Optimization, 2nd ed., Annals of Discrete Mathematics, Vol. 58 (Elsevier, Amsterdam).Google Scholar
• Gallo G, Grigoriadis MD, Tarjan RE (1989) A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18:30–55.Crossref, Google Scholar
• Gordon VS, Tanaev VS (1973) Deadlines in single-stage deterministic scheduling. Optim. Systems Collecting, Transfer Processing Analogous Discrete Data Local Information Comput. Systems. Materials 1st Joint Soviet-Bulgarian Seminar (Institute of Engineering Cybernetics of Bulgarian Academy of Sciences/Institute of Engineering Cybernetics of Belarussian Academy of Sciences, Minsk), 53–58. (in Russian).Google Scholar
• Hochbaum DS, Shamir R (1990) Minimizing the number of tardy job unit under release time constraints. Discr. Appl. Math. 28:45–57.Crossref, Google Scholar
• Horn W (1974) Some simple scheduling algorithms. Naval Res. Logist. Quart. 21:177–185.Crossref, Google Scholar
• Iwata S, Fleischer L, Fujishige S (2001) A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. J. ACM 48:761–777.Crossref, Google Scholar
• Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1993) Sequencing and scheduling: Algorithms and complexity. Graves CS, Rinnooy Kan AHG, Zipkin PH, eds. Handbooks in Operations Research and Management Science, Vol. 4, Logistics of Production and Inventory (North–Holland, Amsterdam),445–522.Google Scholar
• Leung JY-T (2004) Minimizing total weighted error for imprecise computation tasks. Leung JY-T, ed. Handbook of Scheduling: Algorithms, Models and Performance Analysis (Chapman & Hall/CRC, Boca Raton, FL), 34-1–34-16.Crossref, Google Scholar
• Leung JY-T, Yu VKM, Wei W-D (1994) Minimizing the weighted number of tardy task units. Discr. Appl. Math. 51:307–316.Crossref, Google Scholar
• McCormick ST (1999) Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Oper. Res. 47:744–756.Link, Google Scholar
• Nowicki E, Zdrzałka S (1990) A survey of results for sequencing problems with controllable processing times. Discr. Appl. Math. 26:271–287.Crossref, Google Scholar
• Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80:346–355.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• Shabtay D, Steiner G (2007) A survey of scheduling with controllable processing times. Discr. Appl. Math. 155:1643–1666.Crossref, Google Scholar
• Shakhlevich NV, Strusevich VA (2005) Pre-emptive scheduling problems with controllable processing times. J. Sched. 8:233–253.Crossref, Google Scholar
• Shakhlevich NV, Strusevich VA (2008) Preemptive scheduling on uniform parallel machines with controllable job processing times. Algorithmica 51:451–473.Crossref, Google Scholar
• Shakhlevich NV, Shioura A, Strusevich VA (2008) Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times—A polymatroidal approach. Halperin D, Mehlhorn K, eds. Euro. Symposium Algorithms 2008, Lecture Notes in Computer Science, Vol. 5193 (Springer, Berlin), 756–767.Crossref, Google Scholar
• Shakhlevich NV, Shioura A, Strusevich VA (2009) Single machine scheduling with controllable processing times by submodular optimization. Internat. J. Found. Comput. Sci. 20:247–269.Crossref, Google Scholar
• Shih W-K, Lee C-R, Tang CH (2000) A fast algorithm for scheduling imprecise computations with timing constraints to minimize weighted error. Proc. 21st IEEE Real-Time Systems Sympos. (RTSS2000), Orlando, FL, 305–310.Crossref, Google Scholar
• Shih W-K, Liu JWS, Chung J-Y (1991) Algorithms for scheduling imprecise computations with timing constraints. SIAM J. Comput. 20:537–552.Crossref, Google Scholar
• Shih W-K, Liu JWS, Chung J-Y, Gillies DW (1989) Scheduling tasks with ready times and deadlines to minimize average error. ACM SIGOPS Oper. Syst. Rev. 23:14–28.Crossref, Google Scholar
• Shioura A, Shakhlevich NV, Strusevich VA (2013) A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines. SIAM J. Discr. Math. 27:186–204.Crossref, Google Scholar
• Shioura A, Shakhlevich NV, Strusevich VA (2015) Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times. Math. Program., Ser. A. 153:495–534.Crossref, Google Scholar