This paper presents a new model for online decision making. Motivated by the health care delivery application of dynamically allocating patients to procedure rooms in outpatient procedure centers, the online stochastic extensible bin packing problem is described. The objective is to minimize the combined costs of opening procedure rooms and utilizing overtime to complete a … Read more
The traveling umpire problem (TUP) consists of determining which games will be handled by each one of several umpire crews during a double round-robin tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team or venue too … Read more
Valve-point loading affects the input-output characteristics of generating units, bringing the fuel costs nonlinear and nonsmooth. This has been considered in the solution of load dispatch problems, but not in the planning phase of unit commitment. This paper presents a mathematical optimization model for the thermal unit commitment problem considering valve-point loading. The formulation is … Read more
We consider the problem of scheduling jobs on a single machine to minimize the total electricity cost of processing these jobs under time-of-use electricity tariffs. We consider both uniform-speed and speed-scalable machine environments. For the uniform-speed case, we prove that this problem is strongly NP-hard, and in fact inapproximable within a constant factor, unless P … Read more
We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor … Read more
We study a daily mine planning problem where, given a set of blocks we wish to mine, our task is to generate a mining sequence for the excavators such that blending resource constraints are met at various stages of the sequence. Such time-oriented resource constraints are not traditionally handled well by automated planners. On the … Read more
We address a class of deterministic scheduling problems in which two agents compete for the usage of a single machine. The agents have their own objective functions and submit in each round an arbitrary, unprocessed task from their buffer for possible selection. In each round the smaller of the two submitted tasks is chosen and … Read more
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
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
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