A New Robust Optimization Approach for Scheduling under Uncertainty

摘要

The problem of scheduling under uncertainty is addressed. We propose a novel Robust Optimization methodology, which when applied to Mixed-Integer Linear Programming (MILP) problems produces "robust" solutions which are in a sense immune against uncertainty. Both the coefficients and the right-hand-side parameters of the inequalities are considered. Robust Optimization techniques are developed for two forms of uncertain data: unknown distribution but bounded; bounded and symmetric distribution. By introducing a small number of auxiliary variables and applying developments in probability theory, a deterministic robust counterpart problem is formulated to determine the optimal solution given the (relative) magnitude of uncertain data, feasibility tolerance, and "reliability level" when a probabilistic measurement is applied. The Robust Optimization approach is then applied to the scheduling under uncertainty problem. Based on a novel and effective continuous-time short-term scheduling model, three types of the most common sources of uncertainty in scheduling problems can be investigated, namely processing times of operational tasks, market demands for products, and prices of products and raw materials. Preliminary computational results are presented to demonstrate the effectiveness of the proposed approach.