Advanced production scheduling for batch plants in process industries

An Advanced Planning System (APS) offers support at all planning levels along the supply chain while observing limited resources. We consider an APS for process industries (e.g. chemical and pharmaceutical industries) consisting of the modules network design (for long–term decisions), supply network planning (for medium–term decisions), and detailed production scheduling (for short–term decisions). For each module, we outline the decision problem, discuss the specifi cs of process industries, and review state–of–the–art solution approaches. For the module detailed production scheduling, a new solution approach is proposed in the case of batch production, which can solve much larger practical problems than the methods known thus far. The new approach decomposes detailed production scheduling for batch production into batching and batch scheduling. The batching problem converts the primary requirements for products into individual batches, where the work load is to be minimized. We formulate the batching problem as a nonlinear mixed–integer program and transform it into a linear mixed–binary program of moderate size, which can be solved by standard software. The batch scheduling problem allocates the batches to scarce resources such as processing units, workers, and intermediate storage facilities, where some regular objective function like the makespan is to be minimized. The batch scheduling problem is modelled as a resource–constrained project scheduling problem, which can be solved by an efficient truncated branch–and–bound algorithm developed recently. The performance of the new solution procedures for batching and batch scheduling is demonstrated by solving several instances of a case study from process industries.     

Batch scheduling problem for a machinery factory with fixed-position layout

We consider a batch scheduling problem for a two-stage flow shop with fixed-position layout. In the first stage, a fixed number of jobs are assembled on a batch machine with a family batch setup time and a common processing time. In the second stage, the assembled jobs are individually performed for system integration on a discrete machine. The finished job is immediately packed and shipped if the payment has been made; otherwise, it is moved to a temporary storage area, incurring additional removal time. This study develops a mixed integer programming (MIP) to solve the problem of minimising the total completion time and proposes two heuristics for large-size problems. Computational results show that the proposed methods can be applied to resolve real-world problems similar to those in this study.     

BATCH SCHEDULING TO MINIMIZE CYCLE TIME, FLOW TIME, AND PROCESSING COST

We consider a multi-stage batch processing system in which a group of identical units, requiring the same set of operations, is manufactured. In this system, work on the batch must be continuous at each operation, but the batch can be split into sub-batches for transfer between consecutive operations. We examine the case in which operations can be performed in any sequence, using cycle time, total flow time (static and dynamic), and processing cost as measures of performance. It is shown that these problems are closely related to a traveling-salesman problem with a special cost matrix. Optimal scheduling rules are developed for all measures of performance.     

The burn-in test scheduling problem with batch dependent processing time and sequence dependent setup time

The burn-in test scheduling problem (BTSP) is a variation of the complex batch processing machine scheduling problem, which is also a generalisation of the liquid crystal injection scheduling problem with incompatible product families and classical identical parallel machine problem. In the case we investigated on the BTSP, the jobs are clustered by their product families. The product families can be clustered by different product groups. In the same product group, jobs with different product families can be processed as a batch. The batch processing time is dependent on the longest processing time of those jobs in that batch. Setup times between two consecutive batches of different product groups on the same batch machine are sequentially dependent. In addition, the unequal ready times are considered in the BTSP which involves the decisions of batch formation and batch scheduling in order to minimise the total machine workload without violating due dates and the limited machine capacity restrictions. Since the BTSP involves constraints on unequal ready time, batch dependent processing time, and sequence dependent setup times, it is more difficult to solve than the classical parallel batch processing machine scheduling problem with compatible product families or incompatible product families. These restrictions mean that the existing methods cannot be applied into real-world factories directly. Consequently, this paper proposes a mixed integer programming model to solve the BTSP exactly. In addition, two efficient solution procedures which solve the BTSP are also presented.     

A review of: “Progress in Inventory Research.” Edited by ATTILA CHIKAN (Elsevier, 1989.)[Pp.xii+446.] price: US$155·25, Dfl.295·00

We consider the problem of minimizing makespan Cmax on a single batch processing machine in the presence of dynamic job arrivals. The batch processing machine can process up to B jobs simultaneously. The processing time of a batch is given by the processing time of the longest job in the batch. We present polynomial and pseudopolynomial-time algorithms for several special cases, develop efficient heuristics for the general problem and evaluate their performance through extensive computational experiments. Our results indicate that several of the heuristics have an excellent average performance with a modest computational burden.     

Production scheduling of single-stage multi-product batch chemical processes with fixed batch sizes

We address the problem of scheduling a single-stage multi-product batch chemical process with fixed batch sizes. We present a mixed-integer nonlinear programming model to determine the schedule of batches, the batch size, and the number of overtime shifts that satisfy the demand at minimum cost for this process. We introduce a polynomial-time algorithm to solve the problem when the processing times of all batches are identical and the setup and cleaning times are sequence-independent. The solution procedure is based on recognizing that the optimal fixed batch size is a member of a set whose cardinality is polynomial. Given a batch size, the problem may be formulated as an assignment problem. Thus, an optimal solution may be found by iteratively solving a polynomial number of assignment problems. This work was motivated by a pesticide manufacturing company in the design of a new plant where the assumptions of a single bottleneck machine, fixed batch sizes, sequence-independent setup times, and identical batch processing times are all valid. An example is developed for this application.     

Optimal production control policy in unreliable batch processing manufacturing systems with transportation delay

This paper considers the problem of production planning of unreliable batch processing manufacturing systems. The finished goods are produced in lots, and are then transported to a storage area in order to continuously meet a constant demand rate. The main objective of this work is to jointly determine the optimal lot sizing and optimal production control policy that minimise the total expected cost of inventory/backlog and transportation, over an infinite time horizon. The decision variables are the lot sizing and the production rate. The problem is formulated with a stochastic dynamic programming model and the impulse control theory is applied to establish the Hamilton–Jacobi–Bellman (HJB) equations. Based on a numerical resolution of the HJB equations, it is shown that the optimal control policy is governed by a base stock policy for production rate control and economic lot size for batch processing. A thorough analysis and practical issues are addressed with a simulation-based approach. Thus, a combined discrete–continuous simulation model is developed to determine the optimal parameters of the proposed policy when the failure and repair times follow general distributions. The results are illustrated with numerical examples and confirmed through sensitivity analysis.     

Using S-graph to address uncertainty in batch plants

Processes and markets uncertainties make batch plants a complex environment to manage production activities. Uncertainties may cause deviations and infeasibilities in predefined schedules; this may result in poor planning and inefficient utilization of materials. Consequently, the relevance of explicitly incorporating variability in the scheduling formulation in order to offer more efficient plans and robust decisions to changes has become recognized. This work addresses the batch plants scheduling under exogenous uncertainty. The most widely utilized approach to tackle this problem is stochastic programming; however its solution results in high computational expenses. From another standpoint S-graph, a graph-theoretic approach, has proved to be very efficient to deal with deterministic scheduling. In this work, the S-graph framework is enhanced so that stochastic scheduling problems can be handled. For this purpose, a LP model that is used as performance evaluator has been coupled with S-graph framework. One of the main advantages of the proposed approach is that the search space does not increase according to the number of scenarios considered in the problem. Finally, the potential of the proposed framework is highlighted through two illustrative examples.     

Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes

This paper considers the parallel batch processing machine scheduling problem which involves the constraints of unequal ready times, non-identical job sizes, and batch dependent processing times in order to sequence batches on identical parallel batch processing machines with capacity restrictions. This scheduling problem is a practical generalisation of the classical parallel batch processing machine scheduling problem, which has many real-world applications, particularly, in the aging test operation of the module assembly stage in the manufacture of thin film transistor liquid crystal displays (TFT-LCD). The objective of this paper is to seek a schedule with a minimum total completion time for the parallel batch processing machine scheduling problem. A mixed integer linear programming (MILP) model is proposed to optimise the scheduling problem. In addition, to solve the MILP model more efficiently, an effective compound algorithm is proposed to determine the number of batches and to apply this number as one parameter in the MILP model in order to reduce the complexity of the problem. Finally, three efficient heuristic algorithms for solving the large-scale parallel batch processing machine scheduling problem are also provided.     

带成组加工的二阶段柔性流水作业问题

本文仔细剖析混杂二阶段流水作业问题,其中第一阶段由m台同型机组成,第二阶段由一台批处理机M组成,并以最大完工时间Cmax为极小化目标函数.我们证明了该类问题除一种情况有多项式时间可解外,其余情况为(强)NP-hatd的.文中对所有(强)NP-hard情况均给出了近似算法并作了性能比分析.     

A canned food scheduling problem with batch due date

This article considers a canned food scheduling problem where jobs are grouped into several batches. Jobs can be sent to the next operation only when all the jobs in the same batch have finished their processing, i.e. jobs in a batch, have a common due date. This batch due date problem is quite common in canned food factories, but there is no efficient heuristic to solve the problem. The problem can be formulated as an identical parallel machine problem with batch due date to minimize the total tardiness. Since the problem is NP hard, two heuristics are proposed to find the near-optimal solution. Computational results comparing the effectiveness and efficiency of the two proposed heuristics with an existing heuristic are reported and discussed.     

Control of a Batch Processing Machine Serving Compatible Job Families

We consider the control of a single batch processing machine with random arrivals, random processing times, and compatible job families (jobs from different families may be processed together in the same batch, with the processing time distribution of the entire batch determined by the job family in the batch having the greatest expected processing time). The objective is to minimize the long-run average time that jobs spend in the system. We present properties possessed by the optimal policies and discuss the structure of these policies. We next develop a simple heuristic scheduling policy to control the machine. Simulation results are provided to demonstrate the effectiveness of our heuristic over a wide range of problem instances.     

Optimization of multi-product batch plant design under uncertainty with environmental considerations

This paper presents a framework for the design and optimization of multi-product batch processes under uncertainty with environmental considerations. The uncertainties and environmental impacts are discussed. The profit and environmental impacts are considered as bi-objectives for batch plant design. The problem, thus, is formulated as a multi-objective stochastic programming problem. It can be converted into a single-objective two-stage stochastic linear programming problem using the weighted aggregation method. To solve the two-stage stochastic programming, we introduce both Monte Carlo sampling for the entire domain of the distribution function and the feasibility cut method based on dual theory in Benders’ decomposition. The detailed algorithm for problem-solving is presented. A numerical example is presented to illustrate the proposed framework.     

Minimizing total tardiness on a batch processing machine with incompatible job families

Motivated by an application in semiconductor manufacturing, we study the problem of minimizing total tardiness on a batch processing machine with incompatibl8e job families, where all jobs of the same family have identical processing times and jobs of different families cannot be processed together. We present a dynamic programming algorithm which has polynomial time complexity when the number of job families and the batch machine capacity are fixed. We also examine various heuristic solution procedures which can provide near optimal solutions in a reasonable amount of computation time.     

A method combining rules with genetic algorithm for minimizing makespan on a batch processing machine with preventive maintenance

This paper considers the problem of minimising makespan on a single batch processing machine with flexible periodic preventive maintenance. This problem combines two sub-problems, scheduling on a batch processing machine with jobs’ release dates considered and arranging the preventive maintenance activities on a batch processing machine. The preventive maintenance activities are flexible but the maximum continuous working time of the machine, which is allowed, is determined. A mathematical model for integrating flexible periodic preventive maintenance into batch processing machine problem is proposed, in which the grouping of jobs with incompatible job families, the starting time of batches and the preventive maintenance activities are optimised simultaneously. A method combining rules with the genetic algorithm is proposed to solve this model, in which a batching rule is proposed to group jobs with incompatible job families into batches and a modified genetic algorithm is proposed to schedule batches and arrange preventive maintenance activities. The computational results indicate the method is effective under practical problem sizes. In addition, the influences of jobs’ parameters on the performance of the method are analyzed, such as the number of jobs, the number of job families, jobs’ processing time and jobs’ release time.     

Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes

The paper addresses minimizing makespan by a genetic algorithm (GA) for scheduling jobs with non-identical sizes on a single-batch-processing machine. A batch-processing machine can process up to B jobs simultaneously. The processing time of a batch is equal to the longest processing time among all jobs in the batch. Two different GAs are proposed based on different encoding schemes. The first is a sequence-based GA (SGA) that generates random sequences of jobs using GA operators and applies the batch first fit heuristic to group the jobs. The second is a batch-based hybrid GA (BHGA) that generates random batches of jobs using GA operators and ensures feasibility by using knowledge of the problem based on a heuristic procedure. A greedy local search heuristic based on the problem characteristics is hybridized with a BHGA that has the ability of steering efficiently the search toward the optimal or near-optimal schedules. The performance of proposed GAs is compared with a simulated annealing (SA) approach proposed by Melouk et al. (Melouk, S., Damodaran, P. and Chang, P.Y., Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. Int. J. Prod. Econ., 2004, 87, 141–147) and also against a modified lower bound proposed for the problem. Computational results show that BHGA performs considerably well compared with the modified lower bound and significantly outperforms the SGA and SA in terms of both quality of solutions and required runtimes.     

考虑组织学习率-倦怠的SMPEs小组作业模式生产加工周期优化研究

以我国众多中小生产企业人工手工工序作业系统的作业组织模式为研究对象,考虑小组工人在组织学习率-倦怠双因素的影响下,以小组作业模式的生产加工产品批完工时间为目标函数,通过仿真分析得出工人产品批加工生产周期的较优方案。通过例证结果表明：适当休息时间和休息次数,产品批的生产加工周期更优;过长或过短的休息时间和过多或过少的休息次数,都将影响产品批的生产加工周期。     

Heuristic control of multiple batch processors with incompatible job families and future job arrivals

We analyse the problem of minimising the mean cycle time of a batch processing stage containing K?>?1 batch processors in parallel with incompatible job families and future job arrivals. We provide an integer linear programming formulation and a dynamic program formulation for small problem instances. For larger problem instances, we propose an online heuristic policy MPC_REPEAT. At each instance a decision has to be made, MPC_REPEAT decomposes the problem of simultaneously assigning multiple batches to multiple processors into sequentially assigning multiple batches to multiple processors. When job families are uncorrelated, we show via simulation experiments that MPC_REPEAT has significantly lower mean cycle time than a previously proposed look-ahead method except when: (MPC_REPEAT ignores some job families AND the traffic intensity is high.) Our experiments also reveal that increasing the job family correlation of consecutive job arrivals results, with a few exceptions, in a mean cycle-time reduction, for both policies evaluated. This reduction in cycle time generally increases with: increasing number of job families, decreasing number of processors, and increasing time between job arrivals. Our findings imply that controlling the upstream processors, such that job families of consecutive job arrivals are correlated, can reduce the cycle time at the batch processing stage. Furthermore, the expected mean cycle time reduction due to this strategy can be substantially larger than that expected from switching to a more complex batch processing stage policy, under less stringent conditions.     

Scheduling a no-wait flow shop containing unbounded batching machines

We study the problem of scheduling n jobs in a no-wait flow shop consisting of m batching machines. Each job has to be processed by all the machines. All jobs visit the machines in the same order. A job completed on an upstream machine should be immediately transferred to the downstream machine. Batching machines can process several jobs simultaneously in a batch so that all jobs of the same batch start and complete together. The processing time of a batch is equal to the maximum processing time of the jobs in this batch. We assume that the capacity of any batch is unbounded. The problem is to find an optimal batch schedule such that the maximum job completion time, that is the makespan, is minimized. For m = 2, we prove that there exists an optimal schedule with at most two batches and construct such a schedule in O(n log n) time. For m = 3, we prove that the number of batches can be limited to nine and give an example where all optimal schedules have seven batches. Furthermore, we prove that the best schedules with at most one, two and three batches are 3-, 2- and 3/2-approximate solutions, respectively. The first two bounds are tight for corresponding schedules. Finally, we suggest an assignment method that solves the problem with m machines and at most r batches in O(n^{m(r-2)+1+[m/r]}) time, if m and r are fixed. The method can be generalized to minimize an arbitrary maximum cost or total cost objective function.     

Exact and inexact solution procedures for the order picking in an automated carousal conveyor

In many modern logistic systems, automated carousal conveyors are frequently used for storing/retrieving small to medium items to fulfil the customer's demand. The system is used to process a sequence of orders from customers in a dynamic fashion. Each order includes one or several items to be picked from the carousal storage or bin. The sequence between orders and the sequences among items within each order are to be determined, to minimise the total order processing or associated picking cost. This multi-order picking problem is formulated as 0–1 integer programming model, which resembles the well-known Multi-travelling salesman problem. Some important properties of this unique order processing system are described. New theoretical properties are established to characterise the optimal retrieval sequence in an order with multiple items to be picked. Based on these properties, efficient and effective heuristics are developed to solve this multi-order picking problem. The computational detail of these approaches is illustrated by an example. Numerical experiments with problem sizes up to 500 items for a batch of 50 orders are performed, where different order densities and order rates are considered.