Time representations and mathematical models for process scheduling problems

https://doi.org/10.1016/j.compchemeng.2010.07.007Get rights and content

Abstract

During the last 15 years, many mathematical models have been developed in order to solve process operation scheduling problems, using discrete or continuous-time representations. In this paper, we present a unified representation and modeling approach for process scheduling problems. Four different time representations are presented with corresponding strengthened formulations that rely on exploiting the non-overlapping graph structure of these problems through maximum cliques and bicliques. These formulations are compared, and applied to single-stage and multi-stage batch scheduling problems, as well as crude-oil operations scheduling problems. We introduce three solution methods that can be used to achieve global optimality or obtain near-optimal solutions depending on the stopping criterion used. Computational results show that the multi-operation sequencing time representation is superior to the others as it allows efficient symmetry-breaking and requires fewer priority-slots, thus leading to smaller model sizes.

Introduction

Rigorous optimization of real-world problems is often based on advanced programming tools such as mixed-integer linear programming (MILP) or constraint programming (CP, see Rossi, van Beek, & Walsh, 2006). These tools rely on a mathematical or symbolic representation of the problem which is applied by an end-user. In some cases, the relationship between the problem description and its mathematical model is not clear. Therefore an intermediate step is included in the optimization approach (see Fig. 1). In this step, the representation used is detailed and approximations are made. For instance, in the context of scheduling problems, using a discrete-time formulation is in general a constraining approximation of the actual problem, and thus, it may lead to a suboptimal solution as discussed in Floudas and Lin (2004).

Additionally, it is important to note that several mathematical models may be used to obtain the global optimal solution of the problem, which is the best possible solution according to a given optimization criterion. For example, many continuous-time representations rely on a specific parameter representing the number of time-points (Kondili, Pantelides, & Sargent, 1993), time intervals (Lee, Pinto, Grossmann, & Park, 1996), or event points (Ierapetritou & Floudas 1998) used. Therefore, the scheduling problem is represented by an infinite set of mathematical models, one for each possible value of this parameter (all positive integers). The global optimal schedule is the best solution among the optimal solution of all these models. In general, it is not possible to know a priori the parameter value that will lead to the global optimal solution, although it is sometimes possible to derive upper and lower bounds for it. The common trade-off is that global optimality may be guaranteed with a large value of this parameter, which often results in prohibitive solution times.

Many different time representations have been introduced to solve scheduling problems (for review see Floudas & Lin, 2004). Experience has shown that, depending on the characteristics of the problem, some time representations are better suited than others. In this paper, we focus on scheduling problems which rely on:

  • (a)

    a set of possible operations, or actions, that can be performed once, several times, or not at all;

  • (b)

    scheduling decisions that involve both selecting, parametrizing and sequencing the operations that should be executed;

  • (c)

    scheduling constraints such as release dates, due dates, bounds on processing times, non-overlapping constraints, sequence-dependent changeovers, cardinality constraints, and precedence constraints;

  • (d)

    additional side constraints that are used to model more complex features such as limited inventory management or process constraints.

It should be noted that, for example, the selection of operations may correspond to the selection of equipment or discrete resources for tasks in a state-task-network (Kondili et al., 1993) or in a resource-task-network (Pantelides, 1994). In general, operations are defined by fully disaggregating all possible discrete selections of actions in the scheduling system. In contrast, parameterization of operations corresponds to continuous decisions such as batch sizes, transfer volumes, or process operating conditions. The above assumptions do not cover all kinds of scheduling problems but are an important part of the classification presented by Méndez, Cerdá, Grossmann, Harjunkoski, and Fahl (2006). A unique aspect of this paper is that the unifying framework of the models presented in this paper allows it to be applied to multi-stage batch scheduling problems as well as to crude-oil operations scheduling.

The main objective of this work is to develop a unified modeling approach for scheduling problems in order to facilitate the evaluation of several time representations, both in terms of computational time and solution quality. First, a simple scheduling problem is introduced as an example. Next, we study four different types of time representations, which have been used in the literature and clarify the relationships between them. Then, basic MILP models for pure scheduling constraints are presented for each of these time representation. Using concepts from graph theory (cliques and bicliques), we show how these models can be generically strengthened based on the structure of the scheduling problem. Two solution methods are then developed to solve these mathematical formulations. Finally, three types of problems are presented and solved using the different approaches in order to show the effectiveness of the strengthened formulations and to provide elements of comparison between the different time representations.

Section snippets

Case-study

We introduce a small scheduling system that involves six different operations v1,,v6 and three unary resources r1,r2,r3. A unary resource cannot be shared by two or more processing operations at a given time. Table 1 displays resource requirement for each operation. In this case and in the examples studied in this paper, unary resource requirements are handled as non-overlapping constraints between operations. For instance, operations v1 and v4 cannot overlap as they both use resource r1.

Time representations

In this paper, we study four different time representations and show how they can be defined using identical concepts. Each of these make use of priority-slots, which are used to assign and order the executions of operations. The number of priority-slots has to be postulated a priori, and each priority-slot corresponds to a position in a sequence. Whenever an operation is assigned to a priority-slot, it has to be executed with a corresponding scheduling priority. Any operation may be executed

Mathematical models

In this section, we present mathematical models for each time representation. They all rely on the same sets, parameters and variables. Objective functions are not presented here (e.g. minimize makespan, minimize tardiness, or maximize profit) although they can significantly impact the solution of the corresponding formulation.

Strengthened reformulations

The models presented in the previous section may not be effectively solved by MILP solvers. Indeed, special attention needs to be paid to their LP relaxation. As MILP solvers usually perform better when the model has a tight LP relaxation, we introduce strengthened formulations based on the non-overlapping structure of the problem.

Solution methods

Determining the minimum number of priority-slots needed to find the optimal schedule is non-trivial. A commonly used algorithm is to solve several scheduling models, each time increasing the number of priority-slots. We present two different approaches based on this idea followed by the more classic direct approach.

Single-stage batch scheduling problem

In this section, we apply the various time representations to model single-stage batch scheduling problems. We study several instances introduced in Pinto and Grossmann (1995). The largest instance has 29 orders to be processed before given due dates from time 0 to time 30. Four units are available to process each single-stage order. Each unit can process only one order at a time and a minimum unit-specific set-up time is required between any two orders. Each order can only be processed on a

Multi-stage batch scheduling problem

We now extend the previous study to multi-stage batch scheduling problems from Pinto and Grossmann (1995). The largest instance has 10 orders to be processed in 5 consecutive stages before identical due dates t=500 h. Twenty-five units are available to process each order. Each unit is associated to one stage and can process only one order at a time. A minimum unit-specific set-up time is required between any two orders processed on the unit. Each order can only be processed on a subset of all

Crude-oil operations scheduling problem

In this section, the different models are tested using the 4 refinery crude-oil scheduling problem studied in Mouret et al. (2009), noted COSP1, ,COSP4. This problem has been widely studied from the optimization viewpoint since the work of Lee et al. (1996) and Shah (1996). It consists of crude-oil unloading from marine vessels to storage tanks, transfer and blending between tanks, and distillation of crude mixtures. The goal is to maximize profit and meet distillation demands for each type of

Conclusion

In this paper, we have presented four different time representations that in different forms have been previously introduced to solve chemical scheduling problems. Using the common concept of priority-slot, it was shown that it is possible to derive relationship results between these time representations. Additionally, generic scheduling constraints were presented with corresponding strengthened formulations that rely on exploiting the non-overlapping graph structure of these problems through

Acknowledgment

The authors are grateful to Total Raffinage & Marketing for financial support of this project.

References (25)

  • J. Adams et al.

    The shifting bottleneck procedure for job shop scheduling

    Management Science

    (1988)
  • P.M. Castro et al.

    Two new continuous-time models for the scheduling of multistage batch plants with sequence dependent changeovers

    Industrial and Engineering Chemistry Research

    (2006)
  • Cited by (73)

    • Optimal scheduling for simultaneous refinery manufacturing and multi oil-product pipeline distribution

      2022, Computers and Chemical Engineering
      Citation Excerpt :

      In this regard, Ierapetritou and Floudas (1998) proposed a rolling horizon framework for integration of planning and scheduling by a hierarchical decomposition approach. Mouret et al. (2011a, 2011b) studied the integration of refinery planning and scheduling with the multi-operation sequencing representation methods and employed the Lagrangean decomposition approach to solve problems covering the first two subsystems. Given the different time representation nature in crude-oil scheduling (continuous) and refinery planning (discrete), Yang et al. (2020) proposed a multi-scale approach to aggregate continuous and discrete-time formulations in the scheduling and planning sub problems, respectively.

    View all citing articles on Scopus
    View full text