Scheduling

Near-Optimal Solutions and Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling

  • Andreas S. Schulz
  • Nelson A. Uhan
    • Categories Combinatorial Optimization, Scheduling

    We consider the problem of minimizing the weighted sum of completion times on a single machine subject to bipartite precedence constraints where all minimal jobs have unit processing time and zero weight, and all maximal jobs have zero processing time and unit weight. For various probability distributions over these instances–including the uniform distribution–we show several … Read more

    Minimum Dissatisfaction Personnel Scheduling

  • Romulus Andreica
  • Mugurel Ionut Andreica
    • Categories Combinatorial Optimization, Dynamic Programming, Scheduling Tags , , , ,

    In this paper we consider two problems regarding the scheduling of available personnel in order to perform a given quantity of work, which can be arbitrarily decomposed into a sequence of activities. We are interested in schedules which minimize the overall dissatisfaction, where each employee’s dissatisfaction is modeled as a time-dependent linear function. For the … Read more

    Algorithms over Arc-time Indexed Formulations for Single and Parallel Machine Scheduling Problems

  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
  • Rosiane Rodrigues
    • Categories Integer Programming, Scheduling Tags , , ,

    This paper presents algorithms for single and parallel identical machine scheduling problems. While the overall algorithm can be viewed as a branch-cut-and-price over a very large extended formulation, a number of auxiliary techniques are necessary to make the column generation effective. Those techniques include a powerful fixing by reduced costs and a new proposed dual … Read more

    Fast Neighborhood Search For The Single Machine Earliness-Tardiness Scheduling Problem

  • Safia Kedad-Sidhoum
  • Francis Sourd
    • Categories Scheduling Tags , , ,

    This paper addresses the one machine scheduling problem in which $n$ jobs have distinct due dates with earliness and tardiness costs. Fast neighborhoods are proposed for the problem. They are based on a block representation of the schedule and can be computed in $O(n^2)$. A timing operator is presented as well as swap and extract-and-reinsert … Read more

    Optimal Scheduling of File Transfers with Divisible Sizes on Multiple Disjoint Paths

  • Mugurel Ionut Andreica
    • Categories Combinatorial Optimization, Dynamic Programming, Scheduling

    In this paper I investigate several offline and online data transfer scheduling problems and propose efficient algorithms and techniques for addressing them. In the offline case, I present a novel, heuristic, algorithm for scheduling files with divisible sizes on multiple disjoint paths, in order to maximize the total profit (the problem is equivalent to the … Read more

    SHOWCASE SCHEDULING AT FRED ASTAIRE EAST SIDE DANCE STUDIO

  • Miguel A. Lejeune
  • Nevena Yakova
    • Categories Applications - OR and Management Sciences, Scheduling

    The ballroom dancing showcases at Fred Astaire East Side Dance Studio in Manhattan are held at least twice a year and provide the students with an environment for socializing, practice, and improvement. The most important part of a showcase organization is the construction of the dance presentations timetable, and, with the number of participants increasing … Read more

    On-line Service Scheduling

  • Bo Chen
  • Wenxun Xing
  • Zhenbo Wang
    • Categories Approximation Algorithms, Scheduling Tags , , ,

    This paper is concerned with a scheduling problem that occurs in service systems, where customers are classified as `ordinary’ and `special’. Ordinary customers can be served on any service facility, while special customers can be served only on the flexible service facilities. Customers arrive dynamically over time and their needs become known upon arrival. We … Read more

    Clinic Scheduling Models with Overbooking for Patients with Heterogeneous No-show Probabilities

  • Mark Lawley
  • Ayten Turkcan
  • Bo Zeng
  • Ji Lin
    • Categories Production and Logistics, Scheduling Tags , , ,

    Clinical overbooking is intended to reduce the negative impact of patient no-shows on clinic operations and performance. In this paper, we study the clinical scheduling problem with overbooking for heterogeneous patients, i.e. patients who have different no-show probabilities. We consider the objective of maximizing expected profit, which includes revenue from patients and costs associated with … Read more

    Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations

  • M.-C. Plateau
  • Yasmin Rios-Solis
    • Categories Applications - OR and Management Sciences, Quadratic Programming, Scheduling Tags , ,

    In this work, we take advantage of the powerful quadratic programming theory to obtain optimal solutions of scheduling problems. We apply a methodology that starts, in contrast to more classical approaches, by formulating three unrelated parallel machine scheduling problems as 0–1 quadratic programs under linear constraints. By construction, these quadratic programs are non-convex. Therefore, before … Read more

    Approximate Solutions for Deterministic and Stochastic Multi-Dimensional Sequencing

  • B Jothi
  • Sachin Patkar
  • Chandra Poojari
  • Janak Porwal
    • Categories Approximation Algorithms, Scheduling Tags , , , ,

    We investigate the problem of sequencing jobs that have multiple components. Each component of the job needs to be processed independently on a specified machine. We derive approximate algorithms for the problem of scheduling such vector jobs to minimize their total completion time in the deterministic as well as stochastic setting. In particular, we propose … Read more