# Allocation of jobs and resources to work centers

Abstract (Summary)

We examine a stochastic resource allocation problem where simultaneously servers
are partitioned into parallel work centers and job types are assigned to the work
centers. Each job type has a distinct Poisson arrival rate and a distinct work-inprocess
(WIP) weight. The goal is to minimize the expected total WIP cost. Both
identical server and non-identical server problems are considered.
When servers are identical, each work center is a queueing system with an exponential
service time distribution. The problem is solvable in polynomial time if a job
type can be divided between the work centers, and NP-hard if dividing job types is
not allowed. When there are two servers and job types cannot be divided, a heuristic
is constructed where the relative error is bounded above by 4/3. Theoretical Analysis
demonstrates that the heuristic finds an optimal solution for a large class of problem
instances. When there are multiple work centers and job types cannot be divided, a
heuristic is constructed where the relative error is bounded above by 1 + e.
When servers are non-identical, the server assignment discipline has a significant
impact on the WIP cost. Tight lower and upper bounds of the expected system time
function are explored. Heuristics are constructed for the random available server assignment
discipline and the fastest available server assignment discipline. The relative
error for the random available discipline is bounded above by a function of the service
rates. The relative error for the fastest available discipline is bounded above by the
number of servers.
ii
To my parents,
Hsiang Hung and Hsiu-Hsia Liu
iii
Bibliographical Information:

Advisor:

School:The Ohio State University

School Location:USA - Ohio

Source Type:Master's Thesis

Keywords:resource allocation computer scheduling electronic digital computers parallel processing stochastic models queuing theory

ISBN:

Date of Publication: