Allocation of jobs and resources to work centers

by 1973- Hung, Hui-Chih

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