A heuristic algorithm for master production scheduling problem with controllable processing times and scenario-based demands

Master production scheduling (MPS) is widely used by manufacturing industries in order to handle the production scheduling decisions in the production planning hierarchy. The classical approach to MPS assumes infinite capacity, fixed (i.e. non-controllable) processing times and a single pre-determined scenario for the demand forecasts. However, the deterministic optimisation approaches are sometimes not suitable for addressing the real-world problems with high uncertainty and flexibility. Accordingly, in this paper, we propose a new practical model for designing an optimal MPS for the environments in which processing times may be controllable by allocating resources such as facilities, energy or manpower. Due to the NP-hardness of our model, an efficient heuristic algorithm using local search technique and theory of constraints is developed and analysed. The computational results especially for large-sized test problems show that the average optimality gap of proposed algorithm is four times lower than that of exact solution using GAMS while it consumes also significantly smaller run times. Also, the analysis of computational results confirms that considering the controllable processing times may improve the solution space and help to more efficiently utilise the available resources. According to the model structure and performance of the algorithm, it may be proposed for solving large and complex real-world problems particularly the machining and steel industries.     

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.     

Dynamic scheduling of production-assembly networks in a distributed environment

In complex manufacturing environments, meeting the due dates of the jobs and minimizing in process inventories are important performance metrics. One of the common characteristics of complex production systems is production-assembly network of operations. This paper presents an auction-based algorithm for simultaneous scheduling of all manufactured and assembled jobs in a dynamic environment, where the objective function is to minimize both the due date penalties associated with the final products and the inventory cost of the work in process. An auction-based approach using a Mixed-Integer Linear Programming (MILP) model to construct and evaluate the bids so that the auction mechanism mimics a Lagrangian relaxation-based subgradient optimization to ensure global optimality is proposed. The inner structure of the problem enables very efficient calculation of bids for each job or assembly. Using a full factorial experimental design the properties of the proposed algorithm are analyzed. Results show that the proposed auction based algorithm performs better than the popular dispatching rules and is more scalable than the MILP model or direct implementations of the subgradient algorithm. Furthermore, the proposed algorithm is designed to work in a dynamic environment.     

Modelling and symmetry breaking in scheduling problems on batch processing machines

Problems of scheduling batch-processing machines to minimise the makespan are widely exploited in the literature, mainly motivated by real-world applications, such as burn-in tests in the semiconductor industry. These problems consist of grouping jobs in batches and scheduling them on machines. We consider problems where jobs have non-identical sizes and processing times, and the total size of each batch cannot exceed the machine capacity. The processing time of a batch is defined as the longest processing time among all jobs assigned to it. Jobs can also have non-identical release times, and in this case, a batch can only be processed when all jobs assigned to it are available. This paper discusses four different versions of batch scheduling problems, considering a single processing machine or parallel processing machines and considering jobs with or without release times. New mixed integer linear programming formulations are proposed as enhancements of formulations proposed in the literature, and symmetry breaking constraints are investigated to reduce the size of the feasible sets. Computational results show that the proposed formulations have a better performance than other models in the literature, being able to solve to optimality instances only considered before to be solved by heuristic procedures.     

Makespan minimisation on parallel batch processing machines with non-identical job sizes and release dates

The problem we study in this paper arises from the washing step of hospital sterilisation services. Washers in the washing step are capable of handling more than one medical device set as long as their capacity is not exceeded. The medical device set sizes and arrival times to the sterilisation service may be different, but they all have the same washing duration. Thus, we model the washing step as a batch scheduling problem where medical device sets are treated as jobs with non-identical sizes and release dates, but equal processing times. The main findings we present in this paper are the following. First, we study two special cases for which polynomial algorithms are presented. We then develop a 2-approximation algorithm for the general problem. Finally, we develop a MILP model and compare it with another MILP model from the literature. Computational results show that our MILP model outperforms the model from the literature.     

基于变量分离的生产调度空间划分算法

静态生产调度大多形成MILP或MINLP模型，由于调度规模大及混合整数规划的组合优化特性，造成调度求解困难。通过对混合整数规划模型空间的分析，提出依据整数变量和连续变量的分离策略进行空间的自然划分，从而将模型的求解转化为多个较小规模连续子空间的寻优。对典型间歇调度模型的分析表明，将空间划分后进行连续寻优的策略较大地降低了实际运算的规模，降低了求解难度，可以提高问题的求解速度和效率。     

A tabu search algorithm for simultaneous machine/AGV scheduling problem

Machines and automated guided vehicles (AGVs) scheduling problems are two essential issues that need to be addressed for the efficiency of the overall production system. The purpose of this paper is to study the simultaneous scheduling problem of machines and AGVs in a flexible manufacturing system (FMS) since the global optimum cannot be reached by considering each of them individually. In this paper, a mixed integer linear programming (MILP) model is developed with the objective of makespan minimisation. The MILP model consists of the following two constraint sets: machines and AGVs scheduling sub-problems. As both sub-problems are known to be NP-hard, a heuristic algorithm based on tabu search (TS) is proposed to get optimal or near to optimal solution for large-size problems within reasonable computation time. The proposed algorithm includes a novel two-dimensional solution representation and the generation of two neighbour solutions, which are alternately and iteratively applied to improve solutions. Moreover, an improved lower bound calculation method is introduced for the large-size problems. Computational results show the superior performance of the TS algorithm for the simultaneous scheduling problem.     

Robust stochastic mine production scheduling

The production scheduling of open pit mines aims to determine the extraction sequence of blocks such that the net present value (NPV) of a mining project is maximized under capacity and access constraints. This sequencing has significant effect on the profitability of the mining venture. However, given that the values of coefficients in the optimization procedure are obtained in a medium of sparse data and unknown future events, implementations based on deterministic models may lead to destructive consequences to the company. In this article, a robust stochastic optimization (RSO) approach is used to deal with mine production scheduling in a manner such that the solution is insensitive to changes in input data. The approach seeks a trade off between optimality and feasibility. The model is demonstrated on a case study. The findings showed that the approach can be used in mine production scheduling problems efficiently.     

MILP-based campaign scheduling in a specialty chemicals plant: a case study

Supply chain management in chemical process industry focuses on production planning and scheduling to reduce production cost and inventories and simultaneously increase the utilization of production capacities and the service level. These objectives and the specific characteristics of chemical production processes result in complex planning problems. To handle this complexity, advanced planning systems (APS) are implemented and often enhanced by tailor-made optimization algorithms. In this article, we focus on a real-world problem of production planning arising from a specialty chemicals plant. Formulations for finished products comprise several production and refinement processes which result in all types of material flows. Most processes cannot be operated on only one multi-purpose facility, but on a choice of different facilities. Due to sequence dependencies, several batches of identical processes are grouped together to form production campaigns. We describe a method for multicriteria optimization of short- and mid-term production campaign scheduling which is based on a time-continuous MILP formulation. In a preparatory step, deterministic algorithms calculate the structures of the formulations and solve the bills of material for each primary demand. The facility selection for each production campaign is done in a first MILP step. Optimized campaign scheduling is performed in a second step, which again is based on MILP. We show how this method can be successfully adapted to compute optimized schedules even for problem examples of real-world size, and we furthermore outline implementation issues including integration with an APS.     

Mixed-Integer Linear Programming approaches to shelf-life-integrated planning and scheduling in yoghurt production

In the production of perishable products such as dairy, meat or bakery goods, the consideration of shelf life in production planning is of particular importance. Retail customers with relatively low inventory turns can benefit significantly from longer product shelf life as wastage and out-of-stock rates decrease. However, in today's production planning and control systems, shelf-life issues with regard to specific products or customers are only seldom accounted for. Therefore, the objective of this paper is to develop Mixed-Integer Linear Programming (MILP) models that integrate shelf-life issues into production planning and scheduling. The research is based on an industrial case study of yoghurt production. Relying on the principle of block planning, three different MILP models for weekly production planning are presented that apply a combination of a discrete and continuous representation of time. Overnight production and, hence, the necessity for identifying two different shelf-life values for the same production lot is included in the model formulation. Numerical experiments show that near-optimal solutions can be obtained within reasonable computational time.     

A Disjunctive Model for Scheduling in a Manufacturing and Packing Facility with Intermediate Storage

The problem considered in this paper deals with the short term scheduling of a two stage continuous process with intermediate storage tanks. The major scheduling decisions in this problem are: a) the assignment of orders to various storage tanks; b) the sequence of orders in each unit; c) the timing of various operations in different stages. The problem is highly combinatorial in nature. The major challenge is to develop strong integer programming formulations and to devise efficient solution techniques. An initial model is presented in the form of a disjunctive program which is later transformed to a Mixed Integer Linear Programming (MILP) problem. A number of example problems are solved which highlight the limitations of this model as the number of orders increases. A heuristic based on partial preordering is considered which solves industrial sized problems very quickly. The objective function values for the heuristic solutions are within 7% of the optimal values.     

Optimal scheduling for flexible job shop operation

This paper presents a new integer linear programming (ILP) model to schedule flexible job shop, discrete parts manufacturing industries that operate on a make-to-order basis. The model considers groups of parallel homogeneous machines, limited intermediate buffers and negligible set-up effects. Orders consist of a number of discrete units to be produced and follow one of a given number of processing routes. The model allows re-circulation to take place, an important issue in practice that has received scant treatment in the scheduling literature. Good solution times were obtained using commercial mixed-integer linear programming (MILP) software to solve realistic examples of flexible job shops to optimality. This supports the claim that recent advances in computational power and MILP solution algorithms are making this approach competitive with others traditionally applied in job shop scheduling.     

Loading and sequencing heuristics for job scheduling on two unrelated parallel machines with long,sequence-dependent set-up times

The purpose of this paper is to develop and test intelligible heuristics for the scheduling of production orders that can easily be used in practice. Grounded in a case study, this paper examines the combined effects of assignment and sequencing heuristics on commonly used performance indicators. Discrete event simulation is used in the analysis to adequately capture the complexity found in the case study: production orders differing in many aspects, two unrelated parallel machines with varying and product-specific speed, and set-up times that depend on the (dis)similarity of successive orders. Evaluating 108 strategy–scenario combinations including the base case derived from the case study, it is found that a loading heuristic based on order quantity and scheduled capacity in combination with the shortest set-up heuristic performs best. When compared to the heuristic approach used by the case company, this strategy saves about 13.9% of total machine busy time and increases service level by 10.2%. In addition, using a reduced set of 40 production orders we are able to demonstrate that the best heuristic strategies comes close to results generated in a two-stage optimisation. The gap to optimality is only 3.1% in total busy time on average over all scenarios.     

A three-stage decomposition approach for energy-aware scheduling with processing-time-dependent product quality

Due to increasing concerns about energy and environmental demands, decision-makers in industrial companies have developed awareness about energy use and energy efficiency when engaging in short-term production scheduling and planning. This paper studied a flow-shop scheduling problem consisting of a series of processing stages and one final quality check stage with the aim of minimising energy consumption. In particular, the product quality in the problem depends on its processing time at each stage, and the energy consumption is related to the processing speed, equipment state and product quality. A novel three-stage decomposition approach is presented to solve the proposed energy-aware scheduling (EAS) problem. The decomposition approach can drastically reduce the search space and provide reliable solutions for the EAS problem. The numerical experiments show that the computational results can achieve an optimality gap of less than 4% when compared to the global optimal solutions. The parameter analysis demonstrates the managerial implications of the proposed problem. For example, increasing the number of alternative processing speeds or relaxing the delivery date will increase energy efficiency. The energy-saving potential is illustrated by comparing the scheduling results using the proposed approach and human experience.     

Bicriteria scheduling problems involving job rejection,controllable processing times and rate-modifying activity

This paper addresses the bicriteria scheduling problems with simultaneous consideration of job rejection, controllable processing times and rate-modifying activity on a single machine. A job is either rejected, in which case a rejection penalty will be incurred, or accepted and processed on the machine. The rate-modifying activity is an activity on the machine that changes the processing times of the jobs scheduled after the activity. The processing time of a job scheduled after the rate-modifying activity decreases with a job-dependent factor. The processing time of each job can also be controlled by allocating extra resource which is either a linear or a convex function of the amount of a common continuously divisible resource allocated to the job. The objective is to determine the rejected job set, the accepted job sequence, the time (location) of the rate-modifying activity and the resource allocation that jointly find the trade-off between two criteria, where the first criterion is measured as the sum of total completion time and resource consumption cost while the second criterion is the total rejection cost. We consider four different models for treating the two criteria. The computational complexity status and solution procedures are provided for the problems under consideration.     

Novel slack-based robust scheduling rule for a semiconductor manufacturing system with uncertain processing time

The NP-hard scheduling problems of semiconductor manufacturing systems (SMSs) are further complicated by stochastic uncertainties. Reactive scheduling is a common dynamic scheduling approach where the scheduling scheme is refreshed in response to real-time uncertainties. The scheduling scheme is overly sensitive to the emergence of uncertainties because the optimization of performance (such as minimum make-span) and the system robustness cannot be achieved simultaneously by conventional reactive scheduling methods. To improve the robustness of the scheduling scheme, we propose a novel slack-based robust scheduling rule (SR) based on the analysis of robustness measurement for SMS with uncertain processing time. The decision in the SR is made in real time given the robustness. The proposed SR is verified under different scenarios, and the results are compared with the existing heuristic rules. Simulation results show that the proposed SR can effectively improve the robustness of the scheduling scheme with a slight performance loss.     

Hedge against total flow time uncertainty of the uniform parallel machine scheduling problem with interval data

We consider a total flow time minimisation problem of uniform parallel machine scheduling when job processing times are only known to be bounded within certain given intervals. A minmax regret model is proposed to identify a robust schedule that minimises the maximum deviation from the optimal total flow time over all possible realisations of the job processing times. To solve this problem, we first prove that the maximal regret for any schedule can be obtained in polynomial time. Then, we derive a mixed-integer linear programming (MILP) formulation of our problem by exploiting its structural properties. To reduce the computational time, we further transform our problem into a robust single-machine scheduling problem and derive another MILP formulation with fewer variables and constraints. Moreover, we prove that the optimal schedule under the midpoint scenario is a 2-approximation for our minmax regret problem. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.     

Optimization Models for Scheduling of Jobs

This work is motivated by a particular scheduling problem that is faced by logistics centers that perform aircraft maintenance and modification. Here we concentrate on a single facility (hangar) which is equipped with several work stations (bays). Specifically, a number of jobs have already been scheduled for processing at the facility; the starting times, durations, and work station assignments for these jobs are assumed to be known. We are interested in how best to schedule a number of new jobs that the facility will be processing in the near future. We first develop a mixed integer quadratic programming model (MIQP) for this problem. Since the exact solution of this MIQP formulation is time consuming, we develop a heuristic procedure, based on existing bin packing techniques. This heuristic is further enhanced by application of certain local optimality conditions.     

More MILP models for hybrid flow shop scheduling problem and its extended problems

With the rapid development of computer technology and related softwares for mathematical models, mathematical modelling of scheduling problems is receiving growing attention from researchers. In this work, the hybrid flow shop scheduling problem with unrelated parallel machines (HFSP-UPM) with the objective aimed to minimise the makespan is studied. According to the characteristics of the HFSP-UPM, eight mixed integer linear programming (MILP) models are formulated in order to obtain optimal solutions based on different modelling ideas. Then, these models are extended to solve HFSP-UPM with sequence-dependent setup times (HFSP-UPM-SDST), no-wait HFSP-UPM (HFSP-UPM-NW) and HFSP-UPM with blocking (HFSP-UPM-B). All the proposed models and the existing model are detailedly compared and evaluated under three aspects namely modelling process, size complexity and computational complexity. Numerical experiments show that MILP models dependent on diverse modelling ideas perform very differently. The model developed based on stage precedence is the best one and should be given preference in future applications. In addition, the proposed models of HFSP-UPM-NW and HFSP-UPM-B improve several best known solutions for the test instances in the existing literature.     

Multi-objective optimization for the multi-mode finance-based project scheduling problem

The finance-based scheduling problem (FBSP) is about scheduling project activities without exceeding a credit line financing limit. The FBSP is extended to consider different execution modes that result in the multi-mode FBSP (MMFBSP). Unfortunately, researchers have abandoned the development of exact models to solve the FBSP and its extensions. Instead, researchers have heavily relied on the use of heuristics and meta-heuristics, which do not guarantee solution optimality. No exact models are available for contractors who look for optimal solutions to the multi-objective MMFBSP. CPLEX, which is an exact solver, has witnessed a significant decrease in its computation time. Moreover, its current version, CPLEX 12.9, solves multi-objective optimization problems. This study presents a mixed-integer linear programming model for the multi-objective MMFBSP. Using CPLEX 12.9, we discuss several techniques that researchers can use to optimize a multi-objective MMFBSP. We test our model by solving several problems from the literature. We also show how to solve multi-objective optimization problems by using CPLEX 12.9 and how computation time increases as problem size increases. The small increase in computation time compared with possible cost savings make exact models a must for practitioners. Moreover, the linear programming-relaxation of the model, which takes seconds, can provide an excellent lower bound.