| Developments in computing technology coupled with the inability of algorithms based on central control to solve real scheduling problems has led to an increased interest in problem solving over multiple processors, distributed scheduling. Early concepts of distribution were proposed by Duffle (1990) and are characterized by decomposition of data and decision-making among loosely connected autonomous controllers referred as “agents”. The agents encapsulate data and behave motivated by local objectives and constraints. The global system behavior is a consequence of the action and interaction of these decision-makers. In this research two classical scheduling problems with non-regular measures of performance are modeled in this decision structure.; The first problem is the dynamic single machine scheduling problem where the jobs arrive randomly through time. A deterministic dynamic auction-based model for the problem that can be used for a wide range of objectives (e.g., squared deviations, earliness-tardiness penalty, tardiness, flowtime, etc.) and due variables (due dates, due windows, deadlines) is presented. The model uses job forecasts to extract the interactions over time and updates information on a rolling horizon basis. The decision-making and data are decomposed between the job and machine agents. A theoretical basis is presented for problem decomposition, bid construction, and evaluation for the auction using standard math programming tools. Numerical results indicate the model outperforms other distributed implementations in both static and dynamic implementations for a wide range of single machine scheduling problems.; The second problem is the job shop scheduling problem with due dates, windows or deadlines. A new job shop formulation is created and decomposed to model the scheduling problem similar to a combinatorial auction where math-programming tools were used for bid construction and evaluation and both job and machines were involved in the decision-making. This model was executed in two environments—on a single processor and multiple processors connected over the network. Details of communication protocol specifying the information interchanged between distributed solvers along with issues when such a model is implemented over multiple processors over a network are presented. Preliminary results for both implementation environments for different problem sizes, objectives, and due date variables are presented. |
