Single-facility scheduling by logic-based Benders decomposition

Coban, Elvin; Hooker, J.
November 2013
Annals of Operations Research;Nov2013, Vol. 210 Issue 1, p245
Academic Journal
Logic-based Benders decomposition can combine mixed integer programming and constraint programming to solve planning and scheduling problems much faster than either method alone. We find that a similar technique can be beneficial for solving pure scheduling problems as the problem size scales up. We solve single-facility non-preemptive scheduling problems with time windows and long time horizons. The Benders master problem assigns jobs to predefined segments of the time horizon, where the subproblem schedules them. In one version of the problem, jobs may not overlap the segment boundaries (which represent shutdown times, such as weekends), and in another version, there is no such restriction. The objective is to find feasible solutions, minimize makespan, or minimize total tardiness.


Related Articles

  • A Strong Preemptive Relaxation for Weighted Tardiness and Earliness/Tardiness Problems on Unrelated Parallel Machines. Şen, Halil; Bülbül, Kerem // INFORMS Journal on Computing;Winter2015, Vol. 27 Issue 1, p135 

    Research on due date-oriented objectives in the parallel machine environment is at best scarce compared to objectives such as minimizing the makespan or the completion time-related performance measures. Moreover, almost all existing work in this area is focused on the identical parallel machine...

  • AN APPROACH FOR THE OPTIMAL SOLUTION OF MILP PROBLEMS. Ubale, P. V. // Bulletin of Pure & Applied Sciences-Mathematics;Jul-Dec2012, Vol. 31E Issue 2, p169 

    This paper describes an algorithm for finding solutions to optimization problems in which some of the variables must take integer values. The solution of discrete optimization problem to optimality is often an immense job requiring very efficient algorithm. In this paper we describe a Branch and...

  • On reduction of the multistage problem of stochastic programming with quantile criterion to the problem of mixed integer linear programming. Kibzun, A.; Khromova, O. // Automation & Remote Control;Apr2014, Vol. 75 Issue 4, p688 

    Consideration was given to the a priori formulation of the multistage problem of stochastic programming with a quantile criterion which is reducible to the two-stage problem. Equivalence of the two-stage problems with the quantile criterion in the a priori and a posteriori formulations was...

  • A MIP-based framework and its application on a lot sizing problem with setup carryover. Caserta, Marco; Voß, Stefan // Journal of Heuristics;Apr2013, Vol. 19 Issue 2, p295 

    In this paper we present a framework to tackle mixed integer programming problems based upon a 'constrained' black box approach. Given a MIP formulation, a black-box solver, and a set of incumbent solutions, we iteratively build corridors around such solutions by adding exogenous constraints to...

  • Optimal Cardinality Constrained Portfolio Selection. Jianjun Gao; Duan Li // Operations Research;May/Jun2013, Vol. 61 Issue 3, p745 

    One long-standing challenge in both the optimization and investment communities is to devise an efficient algorithm to select a small number of assets from an asset pool such that a portfolio objective is optimized. This cardinality constrained investment situation naturally arises due to the...

  • Undercover: a primal MINLP heuristic exploring a largest sub-MIP. Berthold, Timo; Gleixner, Ambros // Mathematical Programming;Apr2014, Vol. 144 Issue 1/2, p315 

    We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programs (MINLPs) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a smallest set of variables to fix, a so-called cover, such that each...

  • A scenario-based mixed integer linear programming model for composite power system expansion planning with greenhouse gas emission controls. Chang, Mei-Shiang // Clean Technologies & Environmental Policy;Aug2014, Vol. 16 Issue 6, p1001 

    In this paper, the influence of uncertain factors in the power supply system is considered by applying scenario-based programming techniques. A multi-period network design model for composite power system expansion planning is formulated as a mixed integer programming model. This model aims to...

  • A novel probabilistic formulation for locating and sizing emergency medical service stations. Zhang, Zhi-Hai; Li, Kang // Annals of Operations Research;Jun2015, Vol. 229 Issue 1, p813 

    The paper proposes a novel probabilistic model with chance constraints for locating and sizing emergency medical service stations. In this model, the chance constraints are approximated as second-order cone constraints to overcome computational difficulties for practical applications. The...

  • Mathematical programming approaches for dual multicast routing problem with multilayer risk cost. Liang, Zhe; Lee, Chungmok; Chaovalitwongse, W. // Annals of Operations Research;Mar2013, Vol. 203 Issue 1, p101 

    This paper addresses a dual multicast routing problem with shared risk link group (SRLG) diverse costs (DMR-SRLGD) that arises from large-scale distribution of realtime multicast data (e.g., internet protocol TV, videocasting, online games, stock price update). The goal of this problem is to...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics