Scheduling for a processor sharing system with linear slowdown

Ravner, Liron and Nazarathy, Yoni (2017) Scheduling for a processor sharing system with linear slowdown. Mathematical Methods of Operations Research, 1-32. doi:10.1007/s00186-017-0583-3

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Ravner, Liron
Nazarathy, Yoni
Title Scheduling for a processor sharing system with linear slowdown
Journal name Mathematical Methods of Operations Research   Check publisher's open access policy
ISSN 1432-5217
Publication date 2017-03-01
Year available 2017
Sub-type Article (original research)
DOI 10.1007/s00186-017-0583-3
Open Access Status File (Author Post-print)
Start page 1
End page 32
Total pages 32
Place of publication Heidelberg, Germany
Publisher Springer Verlag
Language eng
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 penalty 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.
Keyword Scheduling
Road traffic
Global optimization
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
HERDC Pre-Audit
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Tue, 11 Apr 2017, 00:25:16 EST by Web Cron on behalf of School of Mathematics & Physics