A Strong Preemptive Relaxation for Weighted Tardiness and Earliness/Tardiness Problems on Unrelated Parallel Machines

References

• Azizoglu M, Kirca O (1998) Tardiness minimization on parallel machines. Internat. J. Production Econom. 55(2):163–168.Crossref, Google Scholar
• Azizoglu M, Kirca O (1999a) On the minimization of total weighted flow time with identical and uniform parallel machines. Eur. J. Oper. Res. 113(1):91–100.Crossref, Google Scholar
• Azizoglu M, Kirca O (1999b) Scheduling jobs on unrelated parallel machines to minimize regular total cost functions. IIE Trans. 31(2):153–159.Crossref, Google Scholar
• Baker KR, Scudder GD (1990) Sequencing with earliness and tardiness penalties: A review. Oper. Res. 38(1):22–36.Link, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1):238–252.Crossref, Google Scholar
• Biskup D, Herrmann J, Gupta JN (2008) Scheduling identical parallel machines to minimize total tardiness. Internat. J. Production Econom. 115(1):134–142.Crossref, Google Scholar
• Bülbül K, Kaminsky P, Yano C (2007) Preemption in single machine earliness/tardiness scheduling. J. Sched. 10(4–5):271–292.Crossref, Google Scholar
• Chen Z-L, Lee CY (2002) Parallel machine scheduling with a common due window. Eur. J. Oper. Res. 136(3):512–527.Crossref, Google Scholar
• Chen Z-L, Powell WB (1999a) A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem. Eur. J. Oper. Res. 116(1):220–232.Crossref, Google Scholar
• Chen Z-L, Powell WB (1999b) Solving parallel machine scheduling problems by column generation. INFORMS J. Comput. 11(1): 78–94.Link, Google Scholar
• Cheng TCE, Sin CCS (1990) A state-of-the-art review of parallel-machine scheduling research. Eur. J. Oper. Res. 47(3):271–292.Crossref, Google Scholar
• Detienne B, Dauzère-Pérès S, Yugma C (2011) Scheduling jobs on parallel machines to minimize a regular step total cost function. J. Sched. 14(6):523–538.Crossref, Google Scholar
• Fischetti M, Salvagnin D, Zanette A (2010) A note on the selection of Benders’ cuts. Math. Programming 124(1–2):175–182.Crossref, Google Scholar
• Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. Hammer PL, Johnson EL, Korte BH, eds. Discrete Optimization II, Ann. Discrete Math., Vol. 5 (North-Holland, Amsterdam), 287–326.Crossref, Google Scholar
• IBM ILOG CPLEX (2011) IBM ILOG CPLEX optimization studio 12.4 information center. Accessed April 24, 2013, http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp.Google Scholar
• Jouglet A, Savourey D (2011) Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates. Comput. Oper. Res. 38(9):1259–1266.Crossref, Google Scholar
• Kanet JJ, Sridharan V (2000) Scheduling with inserted idle time: Problem taxonomy and literature review. Oper. Res. 48(1):99–110.Link, Google Scholar
• Kedad-Sidhoum S, Solis YR, Sourd F (2008) Lower bounds for the earliness–tardiness scheduling problem on parallel machines with distinct due dates. Eur. J. Oper. Res. 189(3):1305–1316.Crossref, Google Scholar
• Koulamas C (1997) Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem. Naval Res. Logist. 44(1):109–125.Crossref, Google Scholar
• Lenstra JK, Rinnooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Hammer PL, Johnson EL, Korte BH, Nemhauser GL, eds. Studies in Integer Programming, Ann. Discrete Math., Vol. 1 (North-Holland, Amsterdam), 343–362.Crossref, Google Scholar
• Liaw CF, Lin YK, Cheng CY, Chen M (2003) Scheduling unrelated parallel machines to minimize total weighted tardiness. Comput. Oper. Res. 30(12):1777–1789.Crossref, Google Scholar
• Lin YK, Pfund ME, Fowler JW (2011) Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems. Comput. Oper. Res. 38(6):901–916.Crossref, Google Scholar
• Magnanti TL, Wong RT (1981) Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• Mason SJ, Jin S, Jampani J (2009) A moving block heuristic to minimise earliness and tardiness costs on parallel machines. Internat. J. Prod. Res. 47(19):5377–5390.Crossref, Google Scholar
• M’Hallah R, Al-Khamis T (2012) Minimising total weighted earliness and tardiness on parallel machines using a hybrid heuristic. Internat. J. Prod. Res. 50(10):2639–2664.Crossref, Google Scholar
• Mönch L (2008) Heuristics to minimize total weighted tardiness of jobs on unrelated parallel machines. 2008 IEEE Internat. Conf. Automation Sci. Engrg., Arlington, VA, 572–577.Crossref, Google Scholar
• Pan Y, Shi L (2007) On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems. Math. Programming 110(3):543–559.Crossref, Google Scholar
• Pessoa A, Uchoa E, Aragão MP, Rodrigues R (2010) Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems. Math. Programming Comput. 2(3–4):259–290.Crossref, Google Scholar
• Pinedo M (2008) Scheduling: Theory, Algorithms, and Systems, 3rd ed. (Springer, New York).Google Scholar
• Rubin P (2011) Benders decomposition then and now. Accessed April 24, 2013, http://orinanobworld.blogspot.com/2011/10/benders-decomposition-then-and-now.html.Google Scholar
• Şen H, Bülbül K (2012) A simple, fast, and effective heuristic for the single-machine total weighted tardiness problem. Demeulemeester E, Herroelen W, eds. Proc. 13th Internat. Conf. Project Management and Scheduling (PMS 2012, Leuven, Belgium), 282–286.Google Scholar
• Sen T, Sulek JM, Dileepan P (2003) Static scheduling research to minimize weighted and unweighted tardiness: A state-of-the-art survey. Internat. J. Production Econom. 83(1):1–12.Crossref, Google Scholar
• Shim SO, Kim YD (2007a) Minimizing total tardiness in an unrelated parallel-machine scheduling problem. J. Oper. Res. Soc. 58(3): 346–354.Crossref, Google Scholar
• Shim SO, Kim YD (2007b) Scheduling on parallel identical machines to minimize total tardiness. Eur. J. Oper. Res. 177(1):135–146.Crossref, Google Scholar
• Souayah N, Kacem I, Haouari M, Chu C (2009) Scheduling on parallel identical machines to minimise the total weighted tardiness. Internat. J. Adv. Oper. Management 1(1):30–69.Google Scholar
• Sourd F, Kedad-Sidhoum S (2003) The one-machine problem with earliness and tardiness penalties. J. Sched. 6(6):533–549.Crossref, Google Scholar
• Tanaka S, Araki M (2008) A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines. Internat. J. Production Econom. 113(1):446–458.Crossref, Google Scholar
• Tanaka S, Fujikuma S (2012) A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time. J. Sched. 15(3):347–361.Crossref, Google Scholar
• Tanaka S, Fujikuma S, Araki M (2009) An exact algorithm for single-machine scheduling without machine idle time. J. Sched. 12(6):575–593.Crossref, Google Scholar
• Üster H, Agrahari H (2011) A Benders decomposition approach for a distribution network design problem with consolidation and capacity considerations. Oper. Res. Lett. 39(2):138–143.Crossref, Google Scholar
• van den Akker JM, Hoogeveen JA, van de Velde SL (1999) Parallel machine scheduling by column generation. Oper. Res. 47(6): 862–872.Link, Google Scholar
• Van Roy TJ (1986) A cross decomposition algorithm for capacitated facility location. Oper. Res. 34(1):145–163.Link, Google Scholar
• Wentges P (1996) Accelerating Benders’ decomposition for the capacitated facility location problem. Math. Method Oper. Res. 44(2):267–290.Crossref, Google Scholar
• Yalaoui F, Chu C (2002) Parallel machine scheduling to minimize total tardiness. Internat. J. Production Econom. 76(3):265–279.Crossref, Google Scholar
• Zhou H, Li Z, Wu X (2007) Scheduling unrelated parallel machine to minimize total weighted tardiness using ant colony optimization. 2007 IEEE Inter. Conf. Automation Logist., Jinan, China, 132–136.Crossref, Google Scholar