(496e) Generate Pareto Optimal Solutions for Scheduling Problems Under Uncertainty Using Normal Boundary Intersection Technique

Substantial benefits can be achieved through the use of optimization techniques in plant operations by improving the resource utilization at different levels of decision-making process. However, uncertainty exits in realistic manufacturing environment due to lack of accurate process models and variability of process and environment data. The presence of uncertainty can substantially reduce or eliminate the advantages of optimization approaches. Therefore, it is of great importance to develop systematic methods to address the problem of scheduling under uncertainty. There has been a substantial amount of work addressing the problem of design under uncertainty, while the issue of uncertainty in process operations and specifically in scheduling problems has received relatively little attention.

Balasubramanian and Grossmann [1] considered uncertain processing times in scheduling of multistage flowshop plants. They developed a multiperiod MILP model and proposed a special branch and bound algorithm with aggregated probability model to select the sequence of jobs with minimum expected makespan. Vin and Ierapetritou [6] addressed the problem of multiproduct batch plants scheduling under demand uncertainty. They introduced a robustness metric based on deviations from the expected performance including the infeasible scenarios. Lin et al. [5] proposed a robust optimization method to address the problem of scheduling with uncertain processing times, market demands, or prices. The robust optimization model was derived from its deterministic model considering worst-case values of the uncertain parameters, and a certain infeasibility tolerance was introduced to allow constraint violations. Jia and Ierapetritou [4] developed a branch-and-bound solution framework to discover a set of alternative schedules for a given range of uncertain parameters. The idea of inference based sensitivity analysis for MILP problems was employed that has the advantage of not substantially increasing the complexity compared with the deterministic formulation. Recently, Bonfill et al. [2] used a two-stage stochastic approach to address the robustness in scheduling batch processes with uncertain operation times. The objective is to minimize a weighted combination of the expected makespan and wait times.

In this work, we proposed a multiobjective robust optimization approach so as to incorporate the solution robustness and model robustness in the short-term scheduling formulation. The optimal schedule of the deterministic scheduling formulation will be robust with respect to optimality if it remains close to the optimal solution for any uncertainty realization. This solution is called solution robust. The schedule is also robust with respect to feasibility if it remains feasible for any realization of an uncertain scenario, which is called model robust. Our aim is to find robust schedules in the face of uncertainty that can help the decision maker to select the optimal solution according to his/her preferences. The robust optimization model developed for scheduling problems involves three objectives, which are the expected value of performance (makespan, cost etc.), unsatisfied demand (model robustness), and the upper partial mean of the performance (solution robustness).

NBI is a solution methodology developed by Das and Dennis [3] for generating Pareto surface in nonlinear multiobjective optimization problems. It is proved that this method is independent of the relative scales of the objective functions and is successful in producing an evenly distributed set of points in the Pareto surface given an evenly distributed set of parameters, which is an advantage compared to the most common multiobjective approaches - weighting method and the ε - constraint method.

Assuming the original objective is to minimize the makespan, the basic steps of NBI in the context of scheduling problems include:

Step 1: Determine the anchor points. In order to determine the anchor points, the robust optimization formulation is solved with one objective function being minimized each time.

Step 2: Tighten the anchor points. When model or solution robustness is minimized first, they are fixed at the optimal values and the problem of minimizing the expected makespan is solved again. Thus, the resulting points are the real anchor points that contain the optimal value of the expected makespan corresponding to the finishing time of the last performed task. Then the utopia point which is defined as the vector containing the individual minima of the objectives can be determined correctly.

Step 3: Formulate and solve problem NBIw. Starting from one point on the convex hull of individual minima, NBIw searches on its normal direction towards the utopia point and it stops at the boundary of the feasible region. This problem is solved iteratively for different values of w, which determines the number of Pareto optimal points being generated.

Three scheduling problems are presented to illustrate the results of the proposed approach. The first two examples involve simple production facilities. NBI technique can efficiently generate evenly spread Pareto optimal points, each of which represents a trade-off solution between the expected objective value over all scenarios, feasibility of the schedule and deviation from the expected objective function value. The third case study deals with a crude oil unloading and mixing problem considering two objective functions. A Pareto optimal surface is produced successfully to capture the trade-off between the expected cost and the expected positive deviation. The results presented illustrate the utilization of an efficient multiobjective optimization approach for the solution of scheduling problem under uncertainty leading to the generation of a set of alternative schedules exhibiting competing characteristics in terms of expected performance in the face of uncertainty. Future work includes the development of the multiobjective approach to concentrate of a subset of the Pareto optimal set of solutions in order to reduce the computational cost and avoid the generation of not important optimal solutions.

References:

[1] J. Balasubramanian and I.E. Grossmann. Approximation to multistage stochastic optimization in multiperiod batch plant scheduling under demand uncertainty. Ind. Eng. Chem. Res. 43 (2004).

[2] A. Bonfill, A. Espuna and L. Puigjaner. Addressing robustness in scheduling batch processes with uncertain operations time. Ind. Eng. Chem. Res. 44 (2005).

[3] I. Das and J.E. Dennis. Normal boundary intersection: a new method for generating Pareto optimal points in multicriteria optimization problems, SIAM J. on Optimization. 8 (1998).

[4] Z. Jia and M.G. Ierapetritou. Short-term scheduling under uncertainty using MILP sensitivity analysis. Ind. Eng. Chem. Res. 43 (2004).

[5] X. Lin, S.L. Janak andC.A. Floudas. A new robust optimization approach for scheduling under uncertainty: I. Bounded Uncertainty. Comput. Chem. Eng. 28 (2004).

[6] J.P. Vin and M.G. Ierapetritou. Robust short-term scheduling of multiproduct batch plants under demand uncertainty. Ind. Eng. Chem. Res. 40 (2001).