Scheduling

A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined Into One

  • Shashi Mittal
  • Andreas S. Schulz
    • Categories Approximation Algorithms, Robust Optimization, Scheduling Tags , , ,

    In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the … Read more

    Optimal Job Scheduling with Day-ahead Price and Random Local Distributed Generation: A Two-stage Robust Approach

  • Mehrnaz Abdollahian
  • Bo Zeng
  • Anna Danandeh
  • Long Zhao
    • Categories Robust Optimization, Scheduling Tags , , , ,

    In this paper, we consider a job scheduling problem with random local generation, in which some jobs must be scheduled day-ahead while the others can be scheduled in a real time fashion. To capture the randomness of the local distributed generation, we develop a two-stage robust optimization model by assuming an uncertainty set without probability … Read more

    Simulation Optimization for the Stochastic Economic Lot Scheduling Problem

  • Nils Löhndorf
  • Stefan Minner
    • Categories Dynamic Programming, Optimization of Simulated Systems, Scheduling Tags , , , , ,

    We study simulation optimization methods for the stochastic economic lot scheduling problem. In contrast to prior research, we focus on methods that treat this problem as a black box. Based on a large-scale numerical study, we compare approximate dynamic programming with a global search for parameters of simple control policies. We propose two value function … Read more

    A biased random-key genetic algorithm for job-shop scheduling

  • José Fernando Gonçalves
  • Mauricio G.C. Resende
    • Categories Combinatorial Optimization, Meta Heuristics, Scheduling Tags

    This paper presents a local search, based on a new neighborhood for the job-shop scheduling problem, and its application within a biased random-key genetic algorithm. Schedules are constructed by decoding the chromosome supplied by the genetic algorithm with a procedure that generates active schedules. After an initial schedule is obtained, a local search heuristic, based … Read more

    A biased random-key genetic algorithm for job-shop scheduling

  • José Fernando Gonçalves
    • Categories Combinatorial Optimization, Meta Heuristics, Scheduling Tags

    This paper presents a local search, based on a new neighborhood for the job-shop scheduling problem, and its application within a biased random-key genetic algorithm. Schedules are constructed by decoding the chromosome supplied by the genetic algorithm with a procedure that generates active schedules. After an initial schedule is obtained, a local search heuristic, based … Read more

    Job-Shop Scheduling in a Body Shop

  • Joachim Schauer
  • Cornelius Schwarz
    • Categories Approximation Algorithms, Scheduling Tags , , ,

    We study a generalized job-shop problem called the body shop scheduling problem (bssp). This problem arises from the industrial application of welding in a car body production line, where possible collisions between industrial robots have to be taken into account. bssp corresponds to a job-shop problem where the operations of a job have to follow … Read more

    New VNS heuristic for Total Flowtime Flowshop Scheduling Problem

  • Wagner Emanoel Costa
  • Elizabeth G. Goldbarg
  • Marco César Goldbarg
    • Categories Meta Heuristics, Scheduling Tags , , , ,

    This paper develops a new VNS approach to Permutational Flow shop Scheduling Problem with Total Flow time criterion. There are many hybrid approaches inthe problem’s literature, that make use of VNS internally, usually applying job insert neighbourhood followed by job interchange neighbourhood. In this study different ways to combine both neighbourhoods were examined. All tests … Read more

    Cost-sharing mechanisms for scheduling under general demand settings

  • Sindhura Balireddi
  • Nelson A. Uhan
    • Categories Game Theory, Scheduling

    We investigate cost-sharing mechanisms for scheduling cost-sharing games. We assume that the demand is general—that is, each player can be allocated one of several levels of service. We show how to design mechanisms for these games that are weakly group strategyproof, approximately budget-balanced, and approximately efficient, using approximation algorithms for the underlying scheduling problems. We … Read more

    Symmetry in Scheduling Problems

  • Miguel F. Anjos
  • James Ostrowski
  • Anthony Vannelli
    • Categories Integer Programming, Scheduling Tags , ,

    The presence of symmetry is common in certain types of scheduling problems. Symmetry can occur when one is scheduling a collection of jobs on multiple identical machines, or if one is determining production schedules for identical machines. General symmetry-breaking methods can be strengthened by taking advantage of the special structure of the symmetry group in … Read more

    Robust Unit Commitment Problem with Demand Response and Wind Energy

  • Bo Zeng
  • Long Zhao
    • Categories Robust Optimization, Scheduling Tags , , , ,

    To improve the efficiency in power generation and to reduce the greenhouse gas emission, both Demand Response (DR) strategy and intermittent renewable energy have been proposed or applied in electric power systems. However, the uncertainty and the generation pattern in wind farms and the complexity of demand side management pose huge challenges in power system … Read more