Scheduling for a processor sharing system with linear slowdown
From MaRDI portal
Publication:2408895
Abstract: We consider the problem of scheduling arrivals to a congestion system with a finite number of users having identical deterministic demand sizes. The congestion is of the processor sharing type in the sense that all users in the system at any given time are served simultaneously. However, in contrast to classical processor sharing congestion models, the processing slowdown is proportional to the number of users in the system at any time. That is, the rate of service experienced by all users is linearly decreasing with the number of users. For each user there is an ideal departure time (due date). A centralized scheduling goal is then to select arrival times so as to minimize the total penalty due to deviations from ideal times weighted with sojourn times. Each deviation is assumed quadratic, or more generally convex. But due to the dynamics of the system, the scheduling objective function is non-convex. Specifically, the system objective function is a non-smooth piecewise convex function. Nevertheless, we are able to leverage the structure of the problem to derive an algorithm that finds the global optimum in a (large but) finite number of steps, each involving the solution of a constrained convex program. Further, we put forward several heuristics. The first is the traversal of neighbouring constrained convex programming problems, that is guaranteed to reach a local minimum of the centralized problem. This is a form of a "local search", where we use the problem structure in a novel manner. The second is a one-coordinate "global search", used in coordinate pivot iteration. We then merge these two heuristics into a unified "local-global" heuristic, and numerically illustrate the effectiveness of this heuristic.
Recommendations
Cites work
- ?/M/1: On the equilibrium distribution of customer arrivals
- A Branch-and-Cut Algorithm Without Binary Variables for Nonconvex Piecewise Linear Optimization
- A simplex based algorithm to solve separated continuous linear programs
- A strategic timing of arrivals to a linear slowdown processor sharing system
- Convergence of a block coordinate descent method for nondifferentiable minimization
- scientific article; zbMATH DE number 786521 (Why is no real title available?)
- scientific article; zbMATH DE number 5497553 (Why is no real title available?)
- Integer Polynomial Optimization in Fixed Dimension
- Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions
- Mixed-integer quadratic programming is in NP
- Near optimal control of queueing networks over a finite time horizon
- Performance modeling and design of computer systems. Queueing theory in action
- Rational queueing
- Road congestion
- Scheduling
- Scheduling with batching: A review
- Sequencing with Earliness and Tardiness Penalties: A Review
- Some NP-complete problems in quadratic and nonlinear programming
- The multiple phase service network with generalized processor sharing
Cited in
(4)
This page was built for publication: Scheduling for a processor sharing system with linear slowdown
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408895)
