On-line Service Scheduling

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

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

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

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

A new lower bound for one-machine earliness-tardiness scheduling

In one-machine scheduling, MIP time-indexed formulations are often used to provide very good lower bounds through Lagrangian relaxations. In order to get an improved lower bound, we add valid cuts to a time-indexed formulation and show we still have a Lagrangian relaxation that can be solved as a shortest path in a graph. Two branch-and-bound … Read more

Hybrid heuristics for the permutation flow shop problem

The Flow Shop Problem (FSP) is known to be NP-hard when more than three machines are considered. Thus, for non-trivial size problem instances, heuristics are needed to find good orderings. We consider the permutation case of this problem. For this case, denoted by F|prmu|Cmax, the sequence of jobs has to remain the same at each … Read more

Polyhedral combinatorics of a resource-constrained ordering problem part I: on the partial linear ordering polytope

This paper is the first of a series of two devoted to the polyhedral study of a strongly NP-hard resource-constrained scheduling problem, referred to as the process move programming problem. This problem arises in relation to the operability of certain high-availability real time distributed systems. After a brief introduction to the problem as well as … Read more

Polyhedral combinatorics of a resource-constrained ordering problem part II: on the process move program polytope

This paper is the second of a series of two devoted to the polyhedral study of a strongly NP-hard resource-constrained scheduling problem, referred to as the process move programming problem. In the present paper, we put back into the picture the capacity constraints which were ignored in the first paper. In doing so, we introduce … Read more

Exponential neighborhood search for a parallel machine scheduling problem

We consider the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a restrictive common due date. This problem is NP-hard in the strong sense. In this paper we define an exponential size neighborhood for this problem and prove that finding the local minimum in it is an NP-hard problem. The main contribution … Read more

Approximate resolution of a resource-constrained scheduling problem

This paper is devoted to the approximate resolution of a strongly NP-hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, building on previous research on exact resolution methods, extensive computational results demonstrating its practical … Read more