Minimization of Makespan with Discrete-Time State-Task Network Formulation Christos T. Maravelias, Ignacio E. Grossmann∗ Department of Chemical Engineering, Carnegie Mellon University Pittsburgh, PA 15213, USA Abstract A novel algorithm is proposed for the minimization of makespan of multipurpose batch plants using the State Task Network formulation. The algorithm involves the solution of successive feasibility problems, where the time horizon is extended until a feasible schedule for the given demand is found. To exploit the tight LP relaxation of the STN formulation, a production maximization problem (subject to the given demand) is solved at each iteration and the algorithm terminates when the first feasible solution is found. The algorithm is guaranteed to find an optimal solution, and if integer cuts are used it can provide many alternative solutions. The algorithm appears to be computationally efficient for many classes of problems and process networks of medium complexity. 1. Introduction The State Task Network (STN) formulation was proposed by Kondili et al. (1993) to address the problem of short-term scheduling of multipurpose batch plants. The STN, and its equivalent Resource Task Network (RTN) (Pantelides, 1994) formulation, accounts for complex process network configurations (batch splitting/mixing and recycle streams), variable batch sizes, utility requirements, and various storage policies (NIS/FIS/UIS). The objective function is the maximization of profit over a fixed time horizon. In the discrete-time formulation proposed by Kondili et al. (1993) and refined by Shah et al. (1993) the processing times of tasks are assumed to be constant and the fixed time horizon is divided into time intervals of known duration equal to the greatest common factor of the processing times of all tasks. The assumption of constant processing times is not always realistic, while the length of the intervals may be so small that it either leads to a prohibitive number of intervals rendering the resulting model unsolvable, or else it requires approximations which may compromise the feasibility and optimality of the solution. This has led several authors to develop continuous-time STN/RTN formulations where the time horizon is divided into time intervals of unequal and unknown duration (Schilling and Pantelides, 1996; Zhang and Sargent, 1995; Lee et al., 2001; Maravelias and Grossmann, 2003a). While more realistic, continuous-time formulations are hard to solve mainly due to their poor LP relaxation, which is due to the big-M time matching constraints. In terms of the objective functions, both discrete and continuous-time STN formulations behave moderately well when the objective function is the maximization of profit over a fixed time horizon. In short-term scheduling, however, the demand is usually fixed and more meaningful objectives are the minimization of makespan for a fixed demand, or the minimization of the production cost or the inventory for fixed demands with due dates. For the minimization of makespan, specifically, discrete STN formulations have never been used and continuous STN formulations behave poorly as shown in Maravelias and Grossmann (2003a and 2003b). In this paper we propose a novel algorithm, based on the discrete-time STN formulation, for the minimization of makespan of multipurpose batch plants. To our knowledge, this is the first discrete-time approach for the minimization of makespan. While the known assumptions (constant processing times, ∗ To whom all correspondence should be addressed. E-mail: [email protected] independent setup times, etc.) and limitations (large number of binary variables, need for approximations of processing times) of discrete-time STN models are still present, the proposed model appears to be significantly faster than continuous-time STN models for many classes of problems. 2. Problem Statement We assume that we are given the following items for a batch process: (i) the available units and storage tanks, and their capacities (ii) the available utilities and their upper limits (iii) the production recipe (mass balance coefficients, utility requirements) (iv) the processing time data (v) the amounts of available raw materials and their delivery times (vi) the minimum demand of each of the final products The goal is then to find: (i) the sequence and the timing of tasks taking place in each unit (ii) the batch size of tasks (iii) the allocated resources (iv) the amount of raw materials purchased and the amount of final products produced in order to minimize the makespan or completion time of the corresponding schedule. 3. Proposed Algorithm 3.1. MILP Model of STN The proposed algorithm is based on the discrete STN formulation of Shah et al. (1993), where the binary Wijt is equal to 1 if task i∈I starts on unit j∈J at time t∈T, Bijt is the batch size of task i that starts on unit j at time t, Sst is the inventory level of state s∈S at time t, Rst/Dst are the purchases/sales of state s at time t and Uut is the level of consumption of utility u∈U at time t. tjWjIiptttijti∀∀≤∑∑∈+−=,1)(1'' (1) tjIijWVBWVijtMAXjijtijtMINj∀∈∀∀≤≤ ),(, (2) tsDRBBSSststjsSIjIiijtIisjsSOjIipijtOisststi∀∀−+−+=∑∑∑∑∩∈∩∈−−,)()()()(1ρρ (3) tsCSsst∀∀≤≤ ,0 (4) tsrRstst∀∀≤ , (5) tsdDstst∀∀≥ , (6) ()tuBWUjjIiptijuitijuiuti∀∀+=∑∑∑∈−=−−,)(11)()(θθθβα (7) tuUUMAXuut∀∀≤≤ ,0 (8)3∑∑=tsstsDZζmax (9) Wijt∈{0,1}, Bijt, Sst, Dst, Rst, Uut ≥ 0 (10) Equation (1) is the assignment constraint that ensures that at most one task is assigned to an equipment j at any time. Constraint (2) bounds the batch size of a task within the lower VjMIN and upper VjMAX bounds of the corresponding unit. Equation (3) is the mass balance equation for state s at time t, where ρIis/ρOis are mass fractions for the consumption/production of state s by task i. Constraints (4) – (6) impose bounds on Sst, Rst and Dst, where Cs is the capacity of the storage tank for state s, rst is the availability of state s at time t and dst is the demand of state s at time t. The level of consumption of utility u at time t is calculated through equation (7) where αui and βui are the fixed and variable requirements of task i for utility u. The consumption of utility u at time t is bounded by the