Adaptive multi-period resource allocation

Abstract

For the classical shop scheduling, we apply Pritsker's approach to get a 0-1 IP formulation. This formulation can be adjusted to problems with constraints either no-wait or infinite-wait-buffer. This formulation is further extended to handle (1) multi-machine problems (job-shop or flow-shop), (2)multi-period problems, (3) COS constraints, (4) resource allocation problems.

For general multi-machine shop scheduling problem, a continuous time method is proposed to construct the machine utilization. This method is fundamental for the whole thesis, it is used in the following aspects: (1) to compare the 2 optimal criterion for multi-machine job-shop problems; (2) to build machine capacity relaxation-based heuristics (CH and RH) for flow-shop, bi-directional flow-shop with or without COS constraints; (3) to construct the auction's approach in resource allocation among several scheduling agents;

For the multi-machine job shop problem with infinite wait buffer, we proposed a heuristic method to get a fast feasible solution. The solution quality is compared with CPLEX solution with IP formulation. This heuristic is extendable to handle dynamic batch-job arrival.

For the multi-machine Bi-directional flow shop with COS constraints, 2 heuristics (CH and RH)are proposed and compared with existing greedy method and CPLEX solution. Although CH and RH give better solution than Greedy, the computational time is substantially longer. But if compared with the ScheGen-IP solution, the run time for all heuristic methods are relatively much shorter. The heuristic method works fine for pure {\bf Forward Flow Jobs} with small variance in processing time, when it could achieve real optimal solutions.

The COS constraints not only has meaningful applications, but also provides a new point theoretically. Even the job-sequence has been fixed, the heuristic solutions still make a lot of difference from the optimal one. This is a counter-example for such point by the researchers of genetic algorithm --- optimal sequence will result in optimal solution. %\cite{Ceyda2005}.

The integrated resource allocation is done among several flow-shop scheduling agents, in multi-machine multi-period environment. Our contribution is an adaptive tatonnement auction scheme that comprises two key ideas for price adjustment: the concept of utility pricing and variable step size, along with an algorithm for performing bid generation. Combined with the pre-processing and post-processing steps, the power of the entire system is demonstrated in solving large-scale decentralized scheduling problems.

On utility pricing, we demonstrated both analytically and experimentally that it has a better convergence property than conventional price adjustment schemes with bidding price only. What's more, bidding with utility price does not depend on initial prices, although the cost is an increased communication overhead between auctioneer and bidders. On variable step size, we show experimentally that it performs better than fixed step size with respect to both solution quality and speed, and it is insensitive to the underlying speed function parameters.