Batch scheduling in process industries: an application of resource–constrained project scheduling

The paper deals with batch scheduling problems in process industries where final products arise from several successive chemical or physical transformations of raw materials using multi–purpose equipment. In batch production mode, the total requirements of intermediate and final products are partitioned into batches. The production start of a batch at a given level requires the availability of all input products. We consider the problem of scheduling the production of given batches such that the makespan is minimized. Constraints like minimum and maximum time lags between successive production levels, sequence–dependent facility setup times, finite intermediate storages, production breaks, and time–varying manpower contribute to the complexity of this problem. We propose a new solution approach using models and methods of resource–constrained project scheduling, which (approximately) solves problems of industrial size within a reasonable amount of time. Received: October 15, 1999 / Accepted: March 21, 2000     

Resource–constrained project scheduling: a heuristic for the multi–mode case

This paper presents a heuristic solution procedure for a very general resource–constrained project scheduling problem. Here, multiple execution modes are available for the individual activities of the project. In addition, minimum as well as maximum time lags between different activities may be given. The objective is to determine a mode and a start time for each activity such that the temporal and resource constraints are met and the project duration is minimized. Project scheduling problems of this type occur e.g. in process industries. The heuristic is a multi–pass priority–rule method with backplanning which is based on an integration approach and embedded in random sampling. Its performance is evaluated within an experimental performance analysis for problem instances of real–life size with 100 activities and up to 5 modes per activity.

---

---

Received: September 22, 2000 / Accepted: May 18, 2001     

Iterative algorithms for batching and scheduling to minimise the total job tardiness in two-stage hybrid flow shops

This study considers the batching and scheduling problem in two-stage hybrid flow shops in which each job with a distinct due-date is processed through two serial production stages, each of which has identical machines in parallel. Under the fundamental trade-off that large batch sizes with less frequent changeovers may reduce setup costs and hence increase machine utilisation, while small batch sizes may reduce job flow times and hence improve scheduling performance, the problem is to determine the number of batches, the batch compositions, the allocation of batches to the parallel machines at each stage, and the sequence of the batches allocated to each machine for the objective of minimising the total job tardiness. A mixed integer programming model is developed for the reduced problem in which the number of batches is given, and then, three iterative algorithms are proposed in which batching and scheduling are done repeatedly until a good solution is obtained. To show the performance of the algorithms, computational experiments were done on a number of test instances, and the results are reported. In particular, we show that the number of batches decreases as the ratio of the batch setup time to the job processing time increases.     

An integrated system solution for supply chain optimization in the chemical process industry

This paper considers a complex scheduling problem in the chemical process industry involving batch production. The application described comprises a network of production plants with interdependent production schedules, multi-stage production at multi-purpose facilities, and chain production. The paper addresses three distinct aspects: (i) a scheduling solution obtained from a genetic algorithm based optimizer, (ii) a mechanism for collaborative planning among the involved plants, and (iii) a tool for manual updates and schedule changes. The tailor made optimization algorithm simultaneously considers alternative production paths and facility selection as well as product and resource specific parameters such as batch sizes, and setup and cleanup times. The collaborative planning concept allows all the plants to work simultaneously as partners in a supply chain resulting in higher transparency, greater flexibility, and reduced response time as a whole. The user interface supports monitoring production schedules graphically and provides custom-built utilities for manual changes to the production schedule, investigation of various what-if scenarios, and marketing queries. RID="*" ID="*" The authors would like to thank Hans-Otto Günther and Roland Heilmann for helpful comments on draft versions of this paper.     

A scheduling method for Berth and Quay cranes

This paper discusses a method for scheduling Berth and Quay cranes, which are critical resources in port container terminals. An integer programming model is formulated by considering various practical constraints. A two-phase solution procedure is suggested for solving the mathematical model. The first phase determines the Berthing position and time of each vessel as well as the number of cranes assigned to each vessel at each time segment. The subgradient optimization technique is applied to obtain a near-optimal solution of the first phase. In the second phase, a detailed schedule for each Quay crane is constructed based on the solution found from the first phase. The dynamic programming technique is applied to solve the problem of the second phase. A numerical experiment was conducted to test the performance of the suggested algorithms. RID="*" ID="*" This research has been supported in part by Brain Korea 21 Program (1999–2002). Correspondence to: Y.-M. Park     

Batching and scheduling to minimize the makespan in the two-machine flowshop

In this paper, we consider a class of batching and scheduling problems in the two-machine flowshop where one of the machines is a discrete processor and the other one is a batch processor. The jobs are processed separately on the discrete processor and processed in batches on the batch processor. The processing time of a batch is equal to the total processing time of the jobs contained in it, and the completion time of a job in a batch is defined as the completion time of the batch containing it. A constant setup time is incurred whenever a batch is formed on the batch processor. The problem is to find the optimal batch compositions and the optimal schedule of the batches so that the makespan is minimized. All problems in this class are shown to be NP-complete in the ordinary sense. We also identify some polynomially solvable cases by introducing their corresponding solution methods.     

基于连续时间模型的染缸排产研究

织物的染色是一种按订单生产的批处理过程。每个订单往往被分解成几个批次生产,为了保证质量,要求不同的批次应具有相同的生产环境。因此在对布匹印染的调度过程中,需要确定每个订单的批次,在满足交期的情况下将其分配到恰当的染缸中生产。文中针对印染企业染缸排产困难和布匹浸染的订单交期延迟现象,在合理假设的基础上建立一种连续时间模型。提出了估算时间槽的一种新方法,根据求解出来的时间槽,采用LINGO软件对该模型进行求解。实例证明了该种时间槽估算方法的可行性和有效性。     

An MILP-based approach to the short-term scheduling of make-and-pack continuous production plants

Many fast moving consumers good manufacturing companies produce a moderate number of intermediates that are combined in many different ways to generate an enormous variety of end products. To do that, such companies usually run continuous production plants in a make-to-stock environment. The process structure includes a fabrication area yielding basic intermediates that are stocked in a large middle storage space, and a packing sector where finished products usually comprising several intermediates are manufactured. Intermediates all undergo the same sequence of processing stages and the production of any campaign is sequentially allocated to an ordered set of end products. An MILP continuous time scheduling problem formulation handling independently assignment and sequencing decisions and considering sequence-dependent setup times and specific due dates for export orders has been developed. The problem objective is to meet all end-product demands at minimum make-span. The proposed model is able to account for assorted products, multiple campaigns for a particular intermediate even at the same unit and the consecutive allocation of an intermediate campaign to different finished products. Moreover, it can easily embed powerful preordering rules to yielding reduced MILP formulations so as to tackle real-world industrial problems at low computational cost. The approach has been successfully applied to large-scale industrial examples. RID="*" ID="*" The authors acknowledge financial support from FONCYT under Grant 14-07004, and from “Universidad Nacional del Litoral” under CAI+D 121. Correspondence to: J. Cerdá     

Real-time deadlock-free scheduling for semiconductor track systems based on colored timed Petri nets

This paper addresses the problem of real-time deadlock-free scheduling for a semiconductor track system. The system is required to process wafers continuously, cassette by cassette. The process is not necessarily a repeated one. In addition, the system is deadlock-prone and its modules are failure-prone. Thus, real-time scheduling approaches are required to achieve high-performance. The problem can be solved in a hierarchical way. A deadlock avoidance policy is developed for the system as a lower-layer controller. With the support of the deadlock avoidance policy, heuristic rules are proposed to schedule the system in real-time. An effective modeling tool, colored–timed resource-oriented Petri net, is presented. It is shown that with this model we can schedule a system to achieve satisfactory results in real-time. This method is tolerant to module failures.     

On production batches, transfer batches, and lead times

In this paper we extend a model proposed by Karmarkar for studying the relationship between batch sizes and production lead times. In our extended model we differentiate between production and transfer batches and examine the effect of having smaller transfer batches on lead times. The model is used to obtain optimal transfer batch sizes and determine their relationship to the size of production batches. Further extensions are made to include multiple machines and material-handling considerations and to evaluate their effect on batching decisions. Conditions under which either type of batching can be useful are identified and the corresponding optimal batch sizes are described.     

A coordinated algorithm for integrated production scheduling and vehicle routing problem

In this paper, the integrated production scheduling and vehicle routing problem is considered for a Make-to-Order manufacturer, who has a single machine for production and limited vehicles with capacity constraints for transportation. The objective is to determine production scheduling and vehicle routing, which are two interacted decisions, to minimise the maximum order delivery time. A property on optimal production sequence is proposed first, based on which backward and forward batching methods are developed and are embedded into a proposed genetic algorithm. The proposed genetic algorithm is capable of providing high-quality solutions by determining the two decisions simultaneously. For comparison purpose, a two-stage algorithm is developed, which decomposes the overall problem into two successively solved sub-problems. The experiments show that the proposed genetic algorithm can provide higher quality solutions than the proposed two-stage algorithm and two published algorithms studying related problems.     

Optimal Scheduling of Multiple Feedstock Batch Biogas Production Systems

Biomass to methane production systems have the potential of supplying 25% of the yearly national natural gas demand. The production systems associated with this conversion process are anaerobic digestion facilities. The optimal operation of a batch biomass digester system requires the scheduling of all batches from multiple feedstocks during a fixed time horizon. A significant characteristic of these systems is that the feedstock decays in storage before use in the digester system. The optimal batch residence times in the digester must account for the production rate as well as the decay rate of stored biomass. The availability times, biomass quantities, biogas production rates and storage decay rates must all be taken into account for maximal biogas production to be achieved during the planning horizon. This paper addresses the scheduling of both single and multiple feedstocks in a single digester system. The single feedstock batch scheduling time problem is solved by a dynamic programming algorithm. The multiple feedstock problem is solved by a decomposition approach where the master level allocates time to each feedstock while the subproblems schedule batches within these time allocations.     

A multi-agent system for chemical supply chain simulation and management support

Modern chemical production is customer-driven and the desired delivery time for the products is often shorter than their campaign length. In addition, the raw materials supplying time is often long. These features make it desirable to provide tools to support collaborative supply chain decision making, preferably over the Internet, and where there are conflicts, compromise decisions can be quickly reached and the effects of the decisions can be quantitatively simulated. This paper des cribes such a multi-agent system (MAS) that can be used to simulate the dynamic behaviour and support the management of chemical supply chains over the Internet. Geographically distributed retailers, logistics, warehouses, plants and raw material suppliers are modelled as an open and re-configurable network of co-operative agents, each performing one or more supply chain functions. Communication between agents is made through the common agent communication language KQML (knowledge query message language). A t the simulation layer, the MAS allows distributed simulation of the chain behaviour dynamically, so that compromise decisions can be rapidly and quantitatively evaluated. Because in a chemical supply chain the scheduling of the plant often dominates the chain performance, an optimum scheduling system for batch plants is integrated into the MAS. The functions of the system are illustrated by reference to a case study for the supply and manufacture using a multi-purpose batch plant of paints and coatings.     

Truncated branch-and-bound,schedule-construction,and schedule-improvement procedures for resource-constrained project scheduling

We present heuristic procedures for approximately solving large project scheduling problems with general temporal and resource constraints. In particular, we propose several truncated branch-and-bound techniques, priority-rule methods, and schedule-improvement procedures of types tabu search and genetic algorithm. A detailed experimental performance analysis compares the different heuristics devised and shows that large problem instances with up to 1000 activities and several resources can efficiently be solved with sufficient accuracy.

---

---

Received: July 26, 2000 / Accepted: May 15, 2001     

Planning and scheduling in the process industry

Since there has been tremendous progress in planning and scheduling in the process industry during the last 20 years, it might be worthwhile to give an overview of the current state-of-the-art of planning and scheduling problems in the chemical process industry. This is the purpose of the current review which has the following structure: we start with some conceptional thoughts and some comments on special features of planning and scheduling problems in the process industry. In Section 2 the focus is on planning problems while in Section 3 different types of scheduling problems are discussed. Section 4 presents some solution approaches especially those applied to a benchmark problem which has received considerable interest during the last years. Section 5 allows a short view into the future of planning and scheduling. In the appendix we describe the Westenberger-Kallrath problem which has already been used extensively as a benchmark problem for planning and scheduling in the process industr y.     

Combined strategic and operational planning – an MILP success story in chemical industry

We describe and solve a real world problem in chemical industry which combines operational planning with strategic aspects. In our simultaneous strategic & operational planning (SSDOP) approach we develop a model based on mixed-integer linear (MILP) optimization and apply it to a real-world problem; the approach seems to be applicable in many other situations provided that people in production planning, process development, strategic and financial planning departments cooperate. The problem is related to the supply chain management of a multi-site production network in which production units are subject to purchase, opening or shut-down decisions leading to an MILP model based on a time-indexed formulation. Besides the framework of the SSDOP approach and consistent net present value calculations, this model includes two additional special and original features: a detailed nonlinear price structure for the raw material purchase model, and a detailed discussion of transport times with respect to the time discretization scheme involving a probability concept. In a maximizing net profit scenario the client reports cost saving of several millions US$. The strategic feature present in the model is analyzed in a consistent framework based on the operational planning model, and vice versa. The demand driven operational planning part links consistently to and influences the strategic. Since the results (strategic desicions or designs) have consequences for many years, and depend on demand forecast, raw material availability, and expected costs or sales prices, resp., a careful sensitivity analysis is necessary showing how stable the decisions might be wit h respect to these input data.     

Scheduling a batch processing machine with non-identical job sizes: a clustering perspective

Batch processing machines that process a group of jobs simultaneously are often encountered in semiconductor manufacturing and metal heat treatment. This paper considered the problem of scheduling a batch processing machine from a clustering perspective. We first demonstrated that minimising makespan on a single batching machine with non-identical job sizes can be regarded as a special clustering problem, providing a novel insight into scheduling with batching. The definition of WRB (waste ratio of batch) was then presented, and the objective function of minimising makespan was transformed into minimising weighted WRB so as to define the distance measure between batches in a more understandable way. The equivalence of the two objective functions was also proved. In addition, a clustering algorithm CACB (constrained agglomerative clustering of batches) was proposed based on the definition of WRB. To test the effectiveness of the proposed algorithm, the results obtained from CACB were compared with those from the previous methods, including BFLPT (best-fit longest processing time) heuristic and GA (genetic algorithm). CACB outperforms BFLPT and GA especially for large-scale problems.     

Resource allocation with project management software

We present results of a benchmark test evaluating the resource allocation capabilities of the project management software packages Acos Plus.1 8.2, CA SuperProject 5.0a, CS Project Professional 3.0, MS Project 2000, and Scitor Project Scheduler 8.0.1. The tests are based on 1560 instances of precedence– and resource–constrained project scheduling problems. For different complexity scenarios, we analyze the deviation of the makespan obtained by the software packages from the best feasible makespan known. Among the tested software packages, Acos Plus.1 and Project Scheduler show the best resource allocation performance. Moreover, our numerical analysis reveals a considerable performance gap between the implemented methods and state–of–the–art project scheduling algorithms, especially for large–sized problems. Thus, there is still a significant potential for improving solutions to resource allocation problems in practice.      

Plant co-ordination in pharmaceutics supply networks

The production of active ingredients in the chemical-pharmaceutical industry involves numerous production stages with cumulative lead times of up to two years. Mainly because of rigorous purity requirements and the need of extensive cleaning of the equipment units, production is carried out in campaigns, i.e. multiple batches of the same product type are produced successively before changing to another product type. Each campaign requires a specific configuration of equipment units according to the recipes of the particular chemical process. In the chemical-pharmaceutical industry, production stages are often assigned to different locations, even different countries. Hence the co-ordination of plant operations within the resulting multi-national supply network is of major importance. A key issue is the co-ordination of campaign schedules at different production stages in the various plants. In practice, it is almost impossible to determine exact optimal solutions to the corresponding complex supply network problem with respect to overall logistics costs. In order to reduce the required computational effort, we introduce several aggregation schemes and a novel MILP model formulation which is based on a continuous representation of time. Moreover, we propose an iterative near-optimal solution procedure which can be successfully applied to even exceptionally large real life problem instances. The applicability of the approach suggested is shown using a case study from industry. Correspondence to: H.-O. Günther     

The resource renting problem subject to temporal constraints

We introduce a project scheduling problem subject to temporal constraints where the resource availability costs have to be minimized. As an extension of known project scheduling problems which consider only time-independent costs, this problem includes both time-independent procurement costs and time-dependent renting costs for the resources. Consequently, in addition to projects where all resources are bought, we can deal with projects where resources are rented. Based on the enumeration of a finite set of schedules which is proved to contain an optimal schedule, we develop a depth-first branch-and-bound procedure. Computational experience with a randomly generated test set containing 10800 problem instances is reported.

---

---

Received: December 1, 1999 / Accepted: November 8, 2000