(708e) Systematic Methods for Generating Multiple Alternative Schedules

Active research on production scheduling in the recent decades has led to significant advances in the development of efficient scheduling models and solution methods (Harjunkoski et al. 2014; Velez and Maravelias, 2014). However, despite these advances, there are several challenges in implementing these methods in industrial settings. First, to reduce computational complexity, scheduling models often do not account for detailed processing characteristics, which may lead to infeasible (or low quality) schedules when actually deployed. Second, in industrial applications where the schedules are computed in an online fashion, it is important to find schedules with low nervousness (i.e. the negative impact on the shop floor due to major and/or frequent changes in the schedule), an aspect that is not considered in the models.

One effective and highly desirable, from a practical standpoint, method to address the aforementioned limitations is to generate multiple alternative schedules. This allows the schedulers to choose and deploy schedules that (1) are feasible (when all characteristics are accounted for), and (2) minimize nervousness. Accordingly, in this work, we present methods that allow us to systematically generate multiple alternative schedules. The first method is based on quantifying specific properties of a schedule and penalizing them in the objective function using different weights. We first propose constraints and penalty functions that allow us to generate multiple alternative schedules that are different in terms of (1) the number of batches of task assigned to each unit, (2) the sequencing of batches within each unit, and (3) the presence of idle time in between batches. Next, we propose constraints that quantify changes in schedule in the form of (1) addition/removal of batches, (2) reassignment/time shift of batches, and (3) batch sizes, allowing us to generate alternative schedules with different degrees of nervousness.

Second, we propose an algorithm for obtaining these alternative solutions using parallel computing resources. The parallel computing algorithm employs bound propagation, where the bound information at some computing nodes is used to generate tighter bounds at other nodes. The bounds are generated based on the fact that the models share the same feasible region.

We provide illustrative examples to demonstrate that the proposed methods are capable of finding multiple alternative schedules that are different in terms of the important decisions, such as the number of batches of different tasks assigned to the bottleneck unit. Furthermore, we show that the schedulers can leverage the weight factors to find schedules with desired properties. Finally, through a computational study, we show that the proposed parallel computing algorithm reduces the computational time by more than 50% compared to standard parallel computing methods without bound propagation.

Reference

1. Harjunkoski, I., Maravelias, C. T., Bongers, P., Castro, P. M., Engell, S., Grossmann, I. E., Hooker, J., Mendez, C., Sand, G. and Wassick, J. (2014) Scope for industrial applications of production scheduling models and solution methods. Computers & Chemical Engineering. 62, 161-193.
2. Velez, S. and Maravelias, C. T. (2014) Advances in Mixed-Integer Programming Methods for Chemical Production Scheduling. Annual Review of Chemical and Biomolecular Engineering. 5, 97-121.