A genetic programming approach to solve energy-aware flexible flow-shop scheduling problems with batching and time constraints

Abstract We consider a scheduling problem for two-stage flexible flow shops with parallel batch processing machines (BPMs), motivated by settings found in the diffusion area in semiconductor wafer fabrication facilities. An objective function blending the total weighted tardiness (TWT) and the total electricity cost (TEC) is used under a time-of-use (TOU) tariff. Initial maximum time lags, i.e. time constraints for the operations on the first stage and regular time constraints between the operations on the first and second stage are taken into account to prevent native oxidation and contamination effects on the wafer surface. Problems with time constraints have not been discussed in the literature so far for energy-aware scheduling. A mixed-integer linear programming (MILP) formulation is established for this scheduling problem. Moreover, a genetic programming (GP) procedure is designed to automatically discover priority indices within a new heuristic scheduling framework that is able to avoid time constraint violations. The framework is based on a lead time iteration approach to set internal due dates for the first stage and release dates for the second stage and a time window decomposition (TWD) scheme together with a decision theoretic heuristic (DTH). The GP approach uses specific terminals to avoid the violation of time constraints. Moreover, violations are penalized in the GP approach. Results of designed computational experiments are reported that demonstrate that the learned priority indices lead to high-quality schedules with only a very small number of time constraint violations in a short amount of computing time. Tradeoffs between the TWT and TEC values of the resulting schedules can be obtained by the proposed approach.