Refine
Language
- English (13)
Keywords
- Container terminal (1)
- Integer programming (1)
- Storage space allocation (1)
- Yard crane scheduling (1)
- approximation (1)
- approximation scheme (1)
- competitive analysis (1)
- online (1)
- online scheduling (1)
- scheduling (1)
- stochastic (1)
- sum of weighted completion times (1)
- total weighted completion time (1)
We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.
How to Whack Moles
(2004)
In the classical whack-a-mole game moles that pop up at
certain locations must be whacked by means of a hammer before they
go under ground again. The goal is to maximize the number of moles
caught. This problem can be formulated as an online optimization problem:
Requests (moles) appear over time at points in a metric space and
must be served (whacked) by a server (hammer) before their deadlines
(i.e., before they disappear). An online algorithm learns each request
only at its release time and must base its decisions on incomplete information.
We study the online whack-a-mole problem (wham) on the real
line and on the uniform metric space. While on the line no deterministic
algorithm can achieve a constant competitive ratio, we provide competitive
algorithms for the uniform metric space. Our online investigations
are complemented by complexity results for the offline problem.
We consider a model for scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to traditional stochastic scheduling models, we assume that jobs arrive online, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online scheduling
as a special case. The particular setting we consider is non-preemptive parallel machine scheduling, with the objective to
minimize the total weighted completion times of jobs. We analyze
simple, combinatorial online scheduling policies for that model, and
derive performance guarantees that match performance guarantees previously
known for stochastic and online parallel machine scheduling, respectively.
For processing times that follow NBUE distributions, we
improve upon previously best known performance bounds from
stochastic scheduling, even though we consider a more general
setting.
Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable
first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later.
We introduce the novel concept of an Online Target Date Assignment Problem (OnlineTDAP) as a general framework for online problems with this nature. Requests for the OnlineTDAP become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.g., an appointment with a customer for a
washing machine repair). The cost at a target date is given by the downstream cost, the optimal cost of processing all requests
at that date w.r.t. some fixed downstream offline optimization problem (e.g., the cost of an optimal dispatch for service
technicians). We provide general competitive algorithms for the OnlineTDAP independently of the particular downstream problem,
when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the particular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.
This paper concerns the problem of operating a landside container exchange area that is serviced by multiple semi-automated rail mounted gantry cranes (RMGs) that are moving on a single bi-directional traveling lane. Such a facility is being built by Patrick Corporation at the Port Botany terminal in Sydney. The gantry cranes are a scarce resource and handle the bulk of container
movements. Thus, they require a sophisticated analysis to achieve near optimal utilization. We present a three stage algorithm to manage the container exchange facility, including the scheduling of cranes, the control of associated short-term container stacking, and
the allocation of delivery locations for trucks and other container transporters. The key components of our approach are a time scale decomposition, whereby an integer program controls decisions across a long time horizon to produce a balanced plan that is fed to a series of short time scale online subproblems, and a highly efficient space-time divisioning of short term storage areas.
A computational evaluation shows that our heuristic can find effective solutions for the planning problem; on real-world data it yields a solution at most 8% above a lower bound on optimal RMG utilization.
We consider scheduling on a single machine with one non-availability period to minimize the weighted sum of completion times. We provide a preemptive algorithm with an approximation ratio arbitrarily close to the Golden Ratio,~$(1+\sqrt{5})/2+\eps$, which improves on a previously best known~$2$-approximation. The non-preemptive version of the same algorithm yields a~$(2+\eps)$-approximation.
We consider the preemptive and non-preemptive problems of scheduling jobs with precedence constraints on parallel machines with the
objective to minimize the sum of~(weighted) completion times. We investigate an online model in which the scheduler learns about a
job when all its predecessors have completed. For scheduling on a single machine, we show matching lower and upper bounds of~$\Theta(n)$ and~$\Theta(\sqrt{n})$ for jobs with general and equal weights, respectively. We also derive corresponding results on parallel machines.
Our result for arbitrary job weights holds even in the more general stochastic online scheduling model where, in addition to the limited information about the job set, processing times are uncertain. For a
large class of processing time distributions, we derive also an improved performance guarantee if weights are equal.
We consider a non-preemptive, stochastic parallel machine
scheduling model with the goal to minimize the weighted completion
times of jobs. In contrast to the classical stochastic model where jobs
with their processing time distributions are known beforehand, we assume
that jobs appear one by one, and every job must be assigned
to a machine online. We propose a simple online scheduling policy for
that model, and prove a performance guarantee that matches the currently
best known performance guarantee for stochastic parallel machine
scheduling. For the more general model with job release dates we derive
an analogous result, and for NBUE distributed processing times we
even improve upon the previously best known performance guarantee for
stochastic parallel machine scheduling. Moreover, we derive some lower
bounds on approximation.
We introduce a new technique for solving several sequencing problems. We consider Gilmore and Gomory's variant of the Traveling Salesman Problem and two variants of no-wait flowshop scheduling, the classical makespan minimization problem and a new problem arising in the multistage production process in steel manufacturing.
Our technique is based on an intuitive interpretation of sequencing problems as Eulerian Extension Problems. This view reveals new structural insights and leads to elegant and simple algorithms and proofs for this ancient type of problems. As a major effect, we compute not only a single solution; instead, we represent the entire space of optimal solutions. For the new flowshop scheduling problem we give a full complexity classification for any machine configuration.
Large-scale maintenance in industrial plants requires the entire shutdown of production
units for disassembly, comprehensive inspection and renewal. It is an important process but causes high out-of-service cost. Therefore a good schedule for a shutdown and and an analysis of possible associated risks are crucial for the manufacturer.
We derive models and algorithms for shutdown scheduling that include different features
such as time-cost tradeoff, precedence constraints, hiring external resources, resource leveling, different working shifts, and risk analysis. Our experimental results show that our methods solve large real-world instances very fast and yield an excellent resource utilization. A comparison with solutions of a mixed integer program on smaller instances proves the high quality
of the schedules that our algorithms produce within a few minutes.
Our algorithms work in two phases. The first phase supports the manager in finding a
good makespan for the shutdown. It computes an approximate project time cost tradeoff
curve together with a stochastic evaluation of the risk for meeting a particular makespan t. Our risk measures are the expected tardiness at time t and the probability of completing the shutdown within time t. In the second, detailed planning phase, we solve the actual scheduling optimization problem for the makespan chosen in the first phase heuristically and compute a detailed schedule that respects all side constraints. Again, we complement this by computing
upper bounds for the same two risk measures, but now for the detailed schedule. The shutdown problem has many relationships with well established areas of scheduling, and we also give an overview on the large variety of scheduling problems involved.