Scheduling

A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management

  • Kibaek Kim
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Nonlinear Programming, Scheduling, Stochastic Programming Tags , , , , ,

    We study the problem of integrated staffing and scheduling under demand uncertainty. The problem is formulated as a two-stage stochastic integer program with mixed-integer recourse. The here-and-now decision is to find initial staffing levels and schedules, well ahead in time. The wait-and-see decision is to adjust these schedules at a time epoch closer to the … Read more

    Worst-Case Performance Analysis of Some Approximation Algorithms for Minimizing Makespan and Flow-Time

  • Michael Huang
  • Peruvemba Sundaram Ravi
  • Levent Tunçel
    • Categories Approximation Algorithms, Scheduling Tags , , ,

    In 1976, Coffman and Sethi conjectured that a natural extension of LPT list scheduling to the bicriteria scheduling problem of minimizing makespan over flowtime optimal schedules, called LD algorithm, has a simple worst-case performance bound: (5m-2)/(4m-1) , where m is the number of machines. We study structure of potential minimal counterexamples to this conjecture and … Read more

    Minimizing Value-at-Risk in Single-Machine Scheduling

  • Semih Atakan
  • Kerem Bülbül
  • Nilay Noyan
    • Categories Scheduling

    The vast majority of the machine scheduling literature focuses on deterministic problems in which all data is known with certainty a priori. In practice, this assumption implies that the random parameters in the problem are represented by their point estimates in the scheduling model. The resulting schedules may perform well if the variability in the … Read more

    Scheduling optimization of a real flexible job shop including side constraints regarding maintenance, fixtures, and night shifts

  • Torgny Almgren
  • Michael Patriksson
  • Ann-Brith Strömberg
  • Karin Thörnblad
    • Categories (Mixed) Integer Linear Programming, Production and Logistics, Scheduling Tags , , , , ,

    We present a generic iterative scheduling procedure for the scheduling of a real flexible job shop, the so-called multitask cell at GKN Aerospace Engine Systems in Sweden. A time-indexed formulation of the problem is presented including side constraints regarding preventive maintenance, fixture availability, and unmanned night shifts. This paper continues the work in Thörnblad et … Read more

    A competitive iterative procedure using a time-indexed model for solving flexible job shop scheduling problems

  • Torgny Almgren
  • Michael Patriksson
  • Ann-Brith Strömberg
  • Karin Thörnblad
    • Categories (Mixed) Integer Linear Programming, Production and Logistics, Scheduling Tags , , , , , ,

    We investigate the efficiency of a discretization procedure utilizing a time-indexed mathematical optimization model for finding accurate solutions to flexible job shop scheduling problems considering objectives comprising the makespan and the tardiness of jobs, respectively. The time-indexed model is used to find solutions to these problems by iteratively employing time steps of decreasing length. The … Read more

    Scheduling of Two Agents Task Chains with a Central Selection Mechanism

  • Alessandro Agnetis
  • Gaia Nicosia
  • Ulrich Pferschy
  • Andrea Pacifici
    • Categories Combinatorial Optimization, Game Theory, Scheduling Tags , , ,

    In this paper we address a deterministic scheduling problem in which two agents compete for the usage of a single machine. Each agent decides on a fixed order to submit its tasks to an external coordination subject, who sequences them according to a known priority rule. We consider the problem from different perspectives. First, we … Read more

    Scheduling on uniform nonsimultaneous parallel machines

  • Donald K. Friesen
  • Liliana Grigoriu
    • Categories Approximation Algorithms, Combinatorial Optimization, Scheduling Tags ,

    We consider the problem of scheduling on uniform processors with nonsimultaneous machine available times with the purpose of mini\-mi\-zing the maximum completion time. We give a variant of the Multifit algorithm which generates schedules which end within $1.382$ times the optimal maximum completion times. This results from properties of the Multifit algorithm when used for … Read more

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

  • Kerem Bülbül
  • Halil Sen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Scheduling

    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 environment. In this study, we leverage on our previous work … Read more

    Acceleration and Stabilization Techniques for Column Generation Applied to Capacitated Resource Management Problems

  • Alper Uygur
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Scheduling Tags , , ,

    This research presents a very efficient method of solving a broad class of large-scale capacitated resource management problems by introducing a new formulation and decomposition. A heuristic called Likelihood of Assignment is utilized not only to find high quality initial integer feasible solutions, but also to guide the Branch-and-Price (B&P) Algorithm towards stabilization. Although Column … Read more

    Solving the High School Timetabling Problem to optimality by using ILS algorithms

  • Ademir Aparecido Constantino
  • Haroldo Gambini Santos
  • Wesley Romão
  • Landir Saviniec
    • Categories Meta Heuristics, Scheduling Tags , ,

    The high school timetabling is a classical problem and has many combinatorial variations. It is NP-Complete and since the use of exact methods for this problem is restricted, heuristics are usually employed. This paper applies three Iterated Local Search (ILS) algorithms which includes two newly proposed neighborhood operators to heuristically solve a benchmark of the … Read more