Mixed Integer Linear Programming in Process Scheduling: Modeling,Algorithms, and Applications

This paper reviews the advances of mixed-integer linear programming (MILP) based approaches for the scheduling of chemical processing systems. We focus on the short-term scheduling of general network represented processes. First, the various mathematical models that have been proposed in the literature are classified mainly based on the time representation. Discrete-time and continuous-time models are presented along with their strengths and limitations. Several classes of approaches for improving the computational efficiency in the solution of MILP problems are discussed. Furthermore, a summary of computational experiences and applications is provided. The paper concludes with perspectives on future research directions for MILP based process scheduling technologies.     

Chance constrained programming models for refinery short-term crude oil scheduling problem

The main objective of this work is to put forward chance constrained mixed-integer nonlinear stochastic and fuzzy programming models for refinery short-term crude oil scheduling problem under demands uncertainty of distillation units. The scheduling problem studied has characteristics of discrete events and continuous events coexistence, multistage, multiproduct, nonlinear, uncertainty and large scale. At first, the two models are transformed into their equivalent stochastic and fuzzy mixed-integer linear programming (MILP) models by using the method of Quesada and Grossmann [I. Quesada, I E. Grossmann, Global optimization of bilinear process networks with multicomponent flows, Comput. Chem. Eng. 19 (12) (1995) 1219–1242], respectively. After that, the stochastic equivalent model is converted into its deterministic MILP model through probabilistic theory. The fuzzy equivalent model is transformed into its crisp MILP model relies on the fuzzy theory presented by Liu and Iwamura [B.D. Liu, K. Iwamura, Chance constrained programming with fuzzy parameters, Fuzzy Sets Syst. 94 (2) (1998) 227–237] for the first time in this area. Finally, the two crisp MILP models are solved in LINGO 8.0 based on scheduling time discretization. A case study which has 267 continuous variables, 68 binary variables and 320 constraints is effectively solved with the solution approaches proposed.     

Matheuristic for the decentralized factories scheduling problem

In this study, a novel mixed integer linear programming (MILP) model is developed for the decentralized factories scheduling problem, where a set of transporters is used for shipping goods among parallel factories to minimize the production costs over all of the factories. Due to its typical features, such as multiple heterogeneous factories and transportation times, this problem is extremely difficult to solve, especially for large-scale problems. In order to address this difficulty, the main aim of this study is to develop a new solution algorithm based on the interoperation of metaheuristics and mathematical programming techniques to minimize the production costs for jobs. The algorithm comprises an electromagnetism-like algorithm and variable neighborhood search. In this hybridization based on MILP relaxation, the guiding principle involves the ordering of neighborhood structures. The results obtained by the proposed algorithm and MILP are analyzed and compared for various test problems.     

Robust scheduling of parallel machines with sequence-dependent set-up costs

In this paper we propose a robust approach for solving the scheduling problem of parallel machines with sequence-dependent set-up costs. In the literature, several mathematical models and solution methods have been proposed to solve such scheduling problems, but most of which are based on the strong assumption that input data are known in a deterministic way. In this paper, a fuzzy mathematical programming model is formulated by taking into account the uncertainty in processing times to provide the optimal solution as a trade-off between total set-up cost and robustness in demand satisfaction. The proposed approach requires the solution of a non-linear mixed integer programming (NLMIP), that can be formulated as an equivalent mixed integer linear programming (MILP) model. The resulting MILP model in real applications could be intractable due to its NP-hardness. Therefore, we propose a solution method technique, based on the solution of an approximated model, whose dimension is remarkably reduced with respect to the original counterpart. Numerical experiments conducted on the basis of data taken from a real application show that the average deviation of the reduced model solution over the optimum is less than 1.5%.     

中间品储存约束的多工序批量加工排序问题研究

本文结合生产实际情况，考虑了有限的中间品储存能力所带来的影响，对具有中间品储存约束的多工序批量加工排序问题进行研究。文中利用状态-任务-网络概念和层级模型方法，构建了基于混合整数线性规划的修正排序模型，应用标准优化软件求解。最后用一个算例来说明所构建模型的有效性。     

Sequential Modelling of the Planning and Scheduling Problems of Flexible Manufacturing Systems

Research on the planning and scheduling issues of flexible manufacturing systems (FMS) has not been sparse. Most, if not all, studies, however, have focused on either developing the planning model or examining the performance of different scheduling rules. To date, the FMS planning and scheduling problems have not been studied together, though they are highly interrelated.This paper takes a first step to simultaneously address the planning and scheduling problems of flexible manufacturing systems. The problems are solved as a hierarchical process. We first integrate and formulate batching, loading, and routeing, three of the most important FMS planning problems, as a 0–1 mixed integer program. According to the optimal decisions provided by the integrated planning model, we then develop an off-line scheduling scheme that is capable of generating detail parts sequencing in the sequence independent environment (i.e. the operations are not constrained by a process sequence). Finally, we suggest several extensions and future research directions.     

Modeling demand management strategies for evacuations

Evacuations are massive operations that create heavy travel demand on road networks some of which are experiencing major congestions even with regular traffic demand. Congestion in traffic networks during evacuations, can be eased either by supply or demand management actions. This study focuses on modeling demand management strategies of optimal departure time, optimal destination choice and optimal zone evacuation scheduling (also known as staggered evacuation) under a given fixed evacuation time assumption. The analytical models are developed for a system optimal dynamic traffic assignment problem, so that their characteristics can be studied to produce insights to be used for large-scale solution algorithms. While the first two strategies were represented in a linear programming (LP) model, evacuation zone scheduling problem inevitable included integers and resulted in a mixed integer LP (MILP) one. The dual of the LP produced an optimal assignment principle, and the nature of the MILP formulations revealed clues about more efficient heuristics. The discussed properties of the models are also supported via numerical results from a hypothetical network example.     

A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop

In this paper a new mixed-integer linear programming (MILP) model is proposed for the multi-processor open shop scheduling (MPOS) problems to minimize the makespan with considering independent setup time and sequence dependent removal time. A hybrid imperialist competitive algorithm (ICA) with genetic algorithm (GA) is presented to solve this problem. The parameters of the proposed algorithm are tuned by response surface methodology (RSM). The performance of the algorithm to solve small, medium and large sized instances of the problem is evaluated by introducing two performance metrics. The quality of obtained solutions is compared with that of the optimal solutions for small sized instances and with the lower bounds for medium sized instances. Also some computational results are presented for large sized instances.     

Logic-Based Modeling and Solution of Nonlinear Discrete/Continuous Optimization Problems

This paper presents a review of advances in the mathematical programming approach to discrete/continuous optimization problems. We first present a brief review of MILP and MINLP for the case when these problems are modeled with algebraic equations and inequalities. Since algebraic representations have some limitations such as difficulty of formulation and numerical singularities for the nonlinear case, we consider logic-based modeling as an alternative approach, particularly Generalized Disjunctive Programming (GDP), which the authors have extensively investigated over the last few years. Solution strategies for GDP models are reviewed, including the continuous relaxation of the disjunctive constraints. Also, we briefly review a hybrid model that integrates disjunctive programming and mixed-integer programming. Finally, the global optimization of nonconvex GDP problems is discussed through a two-level branch and bound procedure.     

On the Development of a Mixed-Integer Linear Programming Model for the Flowshop Sequencing Problem

This paper describes the development of a mixed-integer linear programming (MILP) model for the standard N-job, M-machine flowshop sequencing problem. Based on an earlier all-integer model developed by Wagner, this MILP model has been used to solve optimally problems with as many as 25 jobs and as many as 10 machines. Variants of the standard flowshop model, including a variety of performance measures, are also presented. Computational experience involving the successful solution of over 175 flowshop problems is discussed, and suggestions for future research projects are offered.     

A knowledge-based approach to scheduling in an F.M.S.

This paper reports the development of a computer-based system for production scheduling in a dedicated FMS. The system is based on the state-operator framework commonly used in artificial intelligence. Such a system consists of three components: (i) a knowledge base of states, which describes both the current task domain situation and the goal to be achieved; (ii) a set of operators that are used to manipulate the knowledge base; and (iii) a control strategy to decide which operators to apply next and to resolve conflicts. Some of the interesting features of the scheduling system include: (i) the ability to detect resource conflicts; (ii) the ability to determine alternate routes for a given part in the event of a resource conflict; and (iii) the ability to amend plans if an alternate route is found. These features allow the system to take advantage of the flexible routing for parts that an FMS allows. The system has been implemented using the XLISP programming language. Implementation considerations are discussed. A small but comprehensive example is presented. Further research directions are suggested.     

A mathematical model and algorithms for the aircraft hangar maintenance scheduling problem

An aircraft hangar maintenance scheduling problem is studied, motivated by the aircraft heavy maintenance conducted in a hangar operated by an independent maintenance service company. The aircraft hangar maintenance scheduling problem in such context consists of determining a maintenance schedule with minimum penalty costs in fulfilling maintenance requests, and a series of hangar parking plans aligned with the maintenance schedule through the planning period. A mixed-integer linear programming (MILP) mathematical model, integrating the interrelations between the maintenance schedule and aircraft parking layout plans, is presented at first. In the model, the variation of parking capacity of the maintenance hangar and the blocking of the aircraft rolling in and out path are considered. Secondly, the model is enhanced by narrowing down the domain of the time-related decision variables to the possible rolling in and out operations time of each maintenance request. Thirdly, to obtain good quality feasible solutions for large scale instances, a rolling horizon approach incorporating the enhanced mathematical model is presented. The results of computational experiments are reported, showing: (i) the effectiveness of the event-based discrete time MILP model and (ii) the scalability of the rolling horizon approach that is able to provide good feasible solutions for large size instances covering a long planning period.     

Application of operational research models and techniques in flexible manufacturing systems

In this paper, classification of Flexible Manufacturing Systems (FMSs) and flexibilities is presented. It would be difficult to efficiently implement an FMS without solving its design problems. These problems, as well as a number of operations problems, are discussed. A planning and scheduling framework is developed. Based on this framework, the relevant FMS literature is discussed. Most of the tools and techniques applicable for solving FMS problems are listed. Recommendations for future researh are also presented.     

Short-Term Capacity Adjustment with Offline Production for a Flexible Manufacturing System under Abnormal Disturbances

Large production variations caused by abnormal disturbances can significantly reduce the production capacity of a flexible manufacturing system (FMS). To prevent production delays, short-term capacity adjustment strategies can be used to augment the capacity of the FMS, such as working overtime, using alternative tools that are suited for faster processing, and producing parts outside of the FMS. We propose a mixed integer programming (MIP) model to obtain an optimal production plan for a multi-machine FMS. Our model evaluates both the FMS loading decision and the effective use of short-term capacity adjustment strategies to minimize the total part production cost. We develop an iterative procedure to solve the model that uses the Lagrangian relaxation method for finding lower bounds and a Lagrangian heuristic for obtaining feasible solutions. The procedure exploits certain special structures found in the Lagrangian multipliers which enable us to obtain good solutions to reasonably large test problems quickly.     

Optimal periodic scheduling of multipurpose batch plants

A rigorous mathematical programming framework for the scheduling of multipurpose batch plants operated in a cyclic mode is presented. The proposed formulation can deal with batch operations described by complex processing networks, involving shared intermediates, material recycles, and multiple processing routes to the same end-product or intermediate. Batch aggregation and splitting are also allowed. The formulation permits considerable flexibility in the utilisation of processing equipment and storage capacity, and accommodates problems with limited availability of utilities. The scheduling problem is formulated as a large mixed integer linear program (MILP). For a given cycle time, it is shown that it is sufficient for the formulation to characterize a single cycle of the periodic schedule despite the existence of tasks that span two successive cycles. The optimal cycle time is determined by solving a sequence of fixed cycle time problems. The MILP is solved by a branch-and-bound algorithm modified so as to avoid exploring branches that are cyclic permutations of others already fathomed. The resulting implementation permits the solution of problems of realistic size within reasonable computational effort. Several examples are used to illustrate the applicability of the algorithm.     

混合整数规划求解多联票据印刷过程中的生产调度问题

多联票据的印刷过程包括排版、单联印刷和多联配页与装订三个过程。该过程是柔性的流水生产线与装配混合的生产系统。本文研究了该系统中的票据印刷生产调度问题,目标是最小化所有产品的最大完成时间（Makespan）。该问题到目前为止还没有人研究,本文首先建立了该问题的混合整数规划模型,然后提出了该模型的求解方法,并给出了该问题的下界。最后的量化示例和算例试验表明本文的模型是有效的。     

Surgical case scheduling as a generalized job shop scheduling problem

Surgical case scheduling allocates hospital resources to individual surgical cases and decides on the time to perform the surgeries. This task plays a decisive role in utilizing hospital resources efficiently while ensuring quality of care for patients. This paper proposes a new surgical case scheduling approach which uses a novel extension of the Job Shop scheduling problem called multi-mode blocking job shop (MMBJS). It formulates the MMBJS as a mixed integer linear programming (MILP) problem and discusses the use of the MMBJS model for scheduling elective and add-on cases. The model is illustrated by a detailed example, and preliminary computational experiments with the CPLEX solver on practical-sized instances are reported.     

Solution approaches for the soft drink integrated production lot sizing and scheduling problem

In this paper we present a mixed integer programming model that integrates production lot sizing and scheduling decisions of beverage plants with sequence-dependent setup costs and times. The model considers that the industrial process produces soft drink bottles in different flavours and sizes, and it is carried out in two production stages: liquid preparation (stage I) and bottling (stage II). The model also takes into account that the production bottleneck may alternate between stages I and II, and a synchronisation of the production between these stages is required. A relaxation approach and several strategies of the relax-and-fix heuristic are proposed to solve the model. Computational tests with instances generated based on real data from a Brazilian soft drink plant are also presented. The results show that the solution approaches are capable of producing better solutions than those used by the company.     

A hybrid constraint programming approach to?the?log-truck scheduling problem

Scheduling problems in the forest industry have received significant attention in the recent years and have contributed many challenging applications for optimization technologies. This paper proposes a solution method based on constraint programming and mathematical programming for a log-truck scheduling problem. The problem consists of scheduling the transportation of logs between forest areas and woodmills, as well as routing the fleet of vehicles to satisfy these transportation requests. The objective is to minimize the total cost of the non-productive activities such as the waiting time of trucks and forest log-loaders and the empty driven distance of vehicles. We propose a constraint programming model to address the combined scheduling and routing problem and an integer programming model to deal with the optimization of deadheads. Both of these models are combined through the exchange of global constraints. Finally the whole approach is validated on real industrial data.     

Inspection sequencing and part scheduling for flexible manufacturing systems

An approach to the study of integrated effects of inspection sequencing rules and part scheduling policies in flexible manufacturing settings is presented. Simulation experiments were carried out to examine 5 inspection sequencing heuristics while considering 8 different part scheduling policies in a typical FMS construct. Analyses of data have shown that the inspection sequencing has a significant impact on FMS performance, and the selection of a part scheduling policy relies heavily on the inspection plan implemented in the system. The results of this study sustain the need to explore total issues of an FMS, if possible, rather than a piecemeal approach which usually falls short when pursuing a global system optimization.