Integrated process planning and scheduling using an imperialist competitive algorithm

Effective performance of modern manufacturing systems requires integrating process planning and scheduling more tightly, which is consistently challenged by the intrinsic interrelation and intractability of these two problems. Traditionally, these two problems are treated sequentially or separately. Integration of process planning and scheduling (IPPS) provides a valuable approach to improve system performance. However, IPPS is more complex than job shop scheduling or process planning. IPPS is strongly NP-hard in that, compared to an NP-hard job shop scheduling problem with a determined process plan, the process plan for each job in IPPS is also to be optimised. So, an imperialist competitive algorithm (ICA) is proposed to address the IPPS problem with an objective of makespan minimisation. An extended operation-based representation scheme is presented to include information on various flexibilities of process planning with respect to determined job shop scheduling. The main steps of the proposed ICA, including empires construction, assimilation, imperialistic competition, revolution and elimination, are elaborated using an illustrative example. Performance of the proposed ICA was evaluated on four sets of experiments taken from the literature. Computational results of the ICA were compared with that of some existing algorithms developed for IPPS, which validates the efficiency and effectiveness of the ICA in solving the IPPS problem.     

An assessment of the integration of nurse timetable changes with operating room planning and scheduling

The objective of this paper is to understand the links between the management of operating rooms and nurses, and to investigate the trade-offs between the number of operating rooms used, nurses used and overtime work. To do so, we proposed a model that plans and schedules surgical interventions in the operating rooms while considering the availabilities of surgeons and anesthesiologists; the model also includes or discards nurse scheduling. The flexible modeling approach allows us to compare different alternatives, each one representing a different scenario of managing the operating rooms at an operational level. The scenarios were applied to two data-sets and compared on the basis of performance indicators, which include operating costs, utilisation rates of nurses and number of overtime hours done. The important findings were that there is no relationship between the number of nurses required and the number of operating rooms used; the simultaneous scheduling of nurses and surgical interventions provided a better resource usage, a higher occupation rate of nurses, less overtime and furthermore, operating costs were lowered by at least 10% on average.     

Multi-objective process planning and scheduling using controlled elitist non-dominated sorting genetic algorithm

The integration of process planning and scheduling is considered as a critical component in manufacturing systems. In this paper, a multi-objective approach is used to solve the planning and scheduling problem. Three different objectives considered in this work are minimisation of makespan, machining cost and idle time of machines. To solve this integration problem, we propose an improved controlled elitist non-dominated sorting genetic algorithm (NSGA) to take into account the computational intractability of the problem. An illustrative example and five test cases have been taken to demonstrate the capability of the proposed model. The results confirm that the proposed multi-objective optimisation model gives optimal and robust solutions. A comparative study between proposed algorithm, controlled elitist NSGA and NSGA-II show that proposed algorithm significantly reduces scheduling objectives like makespan, cost and idle time, and is computationally more efficient.     

Reducing tardy jobs by integrating process planning and scheduling functions

This paper presents a dynamic approach to reduce tardy jobs through the integration of process planning and scheduling in a batch-manufacturing environment. The developed method aims at re-generating a schedule with fewer tardy jobs, step by step, by exploring the process plan solution space of the tardy jobs. The integrated system comprises a process planning module, a scheduling module, and an integrator module. The process planning module employs an optimisation approach in which the entire plan solution space is first generated and a search algorithm is then used to find the optimal plan, while the scheduling module is based on commonly used heuristics. Based on the job tardiness information of the generated schedule, the integrator module automatically issues a modification order to the process plan solution space of the tardy jobs. The process planning and scheduling modules are then re-run to generate a new plan/schedule solution. Through this iterative process, a satisfactory schedule can be gradually achieved. The uniqueness of this approach is characterised by the flexibility of the process planning strategy, which makes full use of the plan solution space intuitively to achieve a satisfactory schedule. Several examples are presented to confirm the efficacy and the effectiveness of the developed integration system.     

Studying the impact of sequence-dependent set-up times in integrated process planning and scheduling with E-ACO heuristic

In job-shop scheduling, the importance of set-up issues is well known and has been considered in many solution approaches. However, in integrated process planning and scheduling (IPPS) involving flexible process plans, the set-up times are often ignored, or absorbed into processing times in IPPS domain, with the purpose to reduce the complexity. This is based on the assumption that set-up times are sequence-independent, or short enough to be ignored compared to processing times. However, it is not uncommon to encounter sequence-dependent set-up times (SDSTs) in practical production. This paper conducts a detailed investigation on the impact of SDSTs on the practical performance of the schedule: a comparative study is made for different cases where set-up times are (1) separately considered, (2) absorbed into processing times, or (3) totally ignored. An enhanced version of ant colony optimisation (E-ACO) algorithm is used to solve the IPPS problem, with the objective to minimise the total makespan. The following four types of set-up issues are considered: part loading/unloading, fixture preparation, tool switching and material transportation. Situations with various set-up time lengths have been studied and compared. A special case of IPPS problem involving a large number of identical jobs has been specifically studied and discussed. The results have shown that, set-up times should be carefully dealt with under different circumstances.     

GA-based adaptive setup planning toward process planning and scheduling integration

Setup planning of a part for more than one available machine is a typical combinatorial optimisation problem under certain constraints. It has significant impact not only on the whole process planning but also on scheduling, as well as on the integration of process planning and scheduling. Targeting the potential adaptability of process plans associated with setups, a cross-machine setup planning approach using genetic algorithms (GA) for machines with different configurations is presented in this paper. First, based on tool accessibility analysis of different machine configurations, partially sequenced machining features can be grouped into certain setups; then by responding to the requirements from a scheduling system, optimal or near-optimal setup plans are selected for certain criteria, such as cost, makespan and/or machine utilisation. GA is adopted for the combinatorial optimisation, which includes gene pool generation based on tool accessibility examination, setup plan encoding and fitness evaluation, and optimal setup plan selection through GA operations. The proposed approach is implemented in a GA toolbox, and tested using a sample part. The results demonstrate that the proposed approach is applicable to machines with varying configurations, and adaptive to different setup requirements from a scheduling system due to machine availability changes. It is expected that this approach can contribute to process planning and scheduling integration when a process plan is combined with setups for alternative machines during adaptive setup planning.     

A new heuristic for integrated process planning and scheduling in reconfigurable manufacturing systems

Integrated process planning and scheduling (IPPS) is a manufacturing strategy that considers process planning and scheduling as an integrated function rather than two separated functions performed sequentially. In this paper, we propose a new heuristic to IPPS problem for reconfigurable manufacturing systems (RMS). An RMS consists mainly of reconfigurable machine tools (RMTs), each with multiple configurations, and can perform different operations with different capacities. The proposed heuristic takes into account the multi-configuration nature of machines to integrate both process planning and scheduling. To illustrate the applicability and the efficiency of the proposed heuristic, a numerical example is presented where the heuristic is compared to a classical sequential process planning and scheduling strategy using a discrete-event simulation framework. The results show an advantage of the proposed heuristic over the sequential process planning and scheduling strategy.     

A multi-objective optimisation model to integrating flexible process planning and scheduling based on hybrid multi-objective simulated annealing

Process planning and production scheduling play important roles in manufacturing systems. In this paper we present a mixed integer linear programming (MILP) scheduling model, that is to say a slot-based multi-objective multi-product, that readily accounts for sequence-dependent preparation times (transition and set up times or machine changeover time). The proposed scheduling model becomes computationally expensive to solve for long time horizons. The aim is to find a set of high-quality trade-off solutions. This is a combinatorial optimisation problem with substantially large solution space, suggesting that it is highly difficult to find the best solutions with the exact search method. To account for this, the hybrid multi-objective simulated annealing algorithm (MOHSA) is proposed by fully utilising the capability of the exploration search and fast convergence. Two numerical experiments have been performed to demonstrate the effectiveness and robustness of the proposed algorithm.     

Models and algorithms for solving combined vehicle and crew scheduling problems with rest constraints : an application to road feeder service planning in air cargo transportation

We present a mathematical model and two algorithms for solving a complex combined vehicle and crew scheduling problem. The problem arises in the area of road feeder service (RFS) for air cargo transportation where cargo airlines engage specifically equipped RFS-carriers to serve so-called lines, i.e. regular weekly patterns of trips starting and ending at the central hub, respectively. The complexity of the problem stems from the time windows, the rest regulations for drivers and the highly heterogenous requirements with respect to the fleet. The model can be applied to different planning scenarios at the RFS-carrier as well as the airline. The model and method has been incorporated into a decision support system called block.buster where sequences of single trips are combined to feasible blocks starting and ending at the hub and then combined to feasible vehicle round trips.     

Optimisation of integrated process planning and scheduling using a particle swarm optimisation approach

Traditionally, process planning and scheduling are two independent essential functions in a job shop manufacturing environment. In this paper, a unified representation model for integrated process planning and scheduling (IPPS) has been developed. Based on this model, a modern evolutionary algorithm, i.e. the particle swarm optimisation (PSO) algorithm has been employed to optimise the IPPS problem. To explore the search space comprehensively, and to avoid being trapped into local optima, the PSO algorithm has been enhanced with new operators to improve its performance and different criteria, such as makespan, total job tardiness and balanced level of machine utilisation, have been used to evaluate the job performance. To improve the flexibility and agility, a re-planning method has been developed to address the conditions of machine breakdown and new order arrival. Case studies have been used to a verify the performance and efficiency of the modified PSO algorithm under different criteria. A comparison has been made between the result of the modified PSO algorithm and those of the genetic algorithm (GA) and the simulated annealing (SA) algorithm respectively, and different characteristics of the three algorithms are indicated. Case studies show that the developed PSO can generate satisfactory results in optimising the IPPS problem.     

Incorporating supplier selection and order allocation into the vehicle routing and multi-cross-dock scheduling problem

In the vehicle routing problem with cross-docking (VRPCD), it is assumed that the selected suppliers and the quantity of the products purchased from each supplier are known. This paper presents an MILP model which incorporates supplier selection and order allocation into the VRPCD in a multi-cross-dock system minimising the total costs, including purchasing, transportation, cross-docking, inventory and early/tardy delivery penalty costs. The sensitivity of the model on the key parameters of the objective function is analysed and the supply decisions are evaluated when the coefficients of the distribution cost are changed. A two-stage solution algorithm (TSSA) is proposed and the results of the TSSA for small-sized instances are compared with the exact solutions. Finally, a large-sized real case of an urban freight transport is solved using the TSSA.     

Integrated maintenance planning and production scheduling with Markovian deteriorating machine conditions

In many industries, production capacity diminishes as machine conditions deteriorate. Maintenance operations improve machine conditions, but also occupy potential production time, possibly delaying the customer orders. Therefore, one challenge is to determine the joint maintenance and production schedule to minimize the combined costs of maintenance and lost production over the long term. In this paper, we address the problem of integrated maintenance and production scheduling in a deteriorating multi-machine production system over multiple periods. Assuming that at the beginning of each period the demand becomes known and machine conditions are observable, we formulate a Markov decision process model to determine the maintenance plan and develop sufficient conditions guaranteeing its monotonicity in both machine condition and demand. We then formulate an integer programming model to find the maintenance and the production schedule in each period. Our computational results show that exploiting online condition monitoring information in maintenance and production decisions leads to 21% cost savings on average compared to a greedy heuristic and that the benefit of incorporating long-term information in making short-term decisions is highest in industries with medium failure rates.     

Development and challenges of planning and scheduling for petroleum and petrochemical production

Production planning and scheduling are becoming the core of production management, which support the decision of a petrochemical company. The optimization of production planning and scheduling is attempted by every refinery because it gains additional profit and stabilizes the daily production. The optimization problem considered in industry and academic research is of different levels of realism and complexity, thus increasing the gap. Operation research with mathematical programming is a conventional approach used to address the planning and scheduling problem. Additionally, modeling the processes, objectives, and constraints and developing the optimization algorithms are significant for industry and research. This paper introduces the perspective of production planning and scheduling from the development viewpoint.     

控制、规划和调度问题中的博弈论应用

剖析了博弈理论蕴涵的方法论之思想和基本原理,回顾并分析了博弈理论在控制、规划和调度问题中的应用现状,指出了博弈应用研究的要点和今后的研究方向.     

Distributed task scheduling and human resource distribution in industrial service solution production: a simulation application

This paper provides a simulation model for scheduling service task operations and distributing related human resources in dispersed work centres. The managerial concern for the minimisation of temporal overhead costs of task operations in the face of fluctuating, short-term service demands is examined under restrictions imposed by resource availability, work hour flexibility and task-backlog fulfilment. Scheduling strategies are developed directly from the constrained reduction of temporal overheads of appointment and release operations in distributed, non-interlinked work centres. To ensure the model’s structural validity, simulated task backlogs are adjusted to the actual backlog-reducing procedures in real applications. The model provides means for setting up balanced work schedules that can greatly lower temporal overheads of appointment and release operations if workers are selected in accordance with compatible time availability and task qualifications. Direct comparisons of worker productivities in the different centres can also be made, allowing managers to locate bottleneck points of service operations when productivity falls short of desired expectations. The robustness of the model is ensured by finding significant parameter domains through Monte Carlo simulations, centred on data points collected from real-time demand functions in actual service operations.     

Models,algorithms and performance analysis for adaptive operating room scheduling

The complex optimisation problems arising in the scheduling of operating rooms have received considerable attention in recent scientific literature because of their impact on costs, revenues and patient health. For an important part, the complexity stems from the stochastic nature of the problem. In practice, this stochastic nature often leads to schedule adaptations on the day of schedule execution. While operating room performance is thus importantly affected by such adaptations, decision-making on adaptations is hardly addressed in scientific literature. Building on previous literature on adaptive scheduling, we develop adaptive operating room scheduling models and problems, and analyse the performance of corresponding adaptive scheduling policies. As previously proposed (fully) adaptive scheduling models and policies are infeasible in operating room scheduling practice, we extend adaptive scheduling theory by introducing the novel concept of committing. Moreover, the core of the proposed adaptive policies with committing is formed by a new, exact, pseudo-polynomial algorithm to solve a general class of stochastic knapsack problems. Using these theoretical advances, we present performance analysis on practical problems, using data from existing literature as well as real-life data from the largest academic medical centre in The Netherlands. The analysis shows that the practically feasible, basic, 1-level policy already brings substantial and statistically significant improvement over static policies. Moreover, as a rule of thumb, scheduling surgeries with large mean duration or standard deviation early appears good practice.     

Integrated multi-factory production and distribution scheduling applying vehicle routing approach

This paper introduces a new integrated multi-factory production and distribution scheduling problem in supply chain management. This supply chain consists of a number of factories joined together in a network configuration. The factories produce intermediate or finished products and supply them to other factories or to end customers that are distributed in various geographical zones. The problem consists of finding a production schedule together with a vehicle routing solution simultaneously to minimise the sum of tardiness cost and transportation cost. A mixed-integer programming model is developed to tackle the small-sized problems using CPLEX, optimally. Due to the NP-hardness, to deal with medium- and large-sized instances, this paper develops a novel Improved Imperialist Competitive Algorithm (IICA) employing a local search based on simulated annealing algorithm. Performance of the proposed IICA is compared with the optimal solution and also with four variants of population-based metaheuristics: Imperialist Competitive Algorithm, Genetic Algorithm, Particle Swarm Optimisation (PSO), and Improved PSO. Based on the computational results, it is statistically shown that quality of the IICA’s solutions is the same as optimal ones solving small problems. It also outperforms other algorithms in finding near-optimal solutions dealing with medium and large instances in a reasonably short running time.     

More MILP models for integrated process planning and scheduling

The integration of process planning and scheduling is important for an efficient utilisation of manufacturing resources. In general, there are two types of models for this problem. Although some MILP models have been reported, most existing models belong to the first type and they cannot realise a true integration of process planning and scheduling. Especially, they are completely powerless to deal with the cases where jobs are expressed by network graphs because generating all the process plans from a network graph is difficult and inefficient. The network graph-specific models belong to the other type, and they have seldom been deliberated on. In this research, some novel MILP models for integrated process planning and scheduling in a job shop flexible manufacturing system are developed. By introducing some network graph-oriented constraints to accommodate different operation permutations, the proposed models are able to express and utilise flexibilities contained in network graphs, and hence have the power to solve network graph-based instances. The established models have been tested on typical test bed instances to verify their correctness. Computational results show that this research achieves the anticipant purpose: the proposed models are capable of solving network graph-based instances.     

Economic lot and supply scheduling problem: a time-varying lot sizes approach

We study the economic lot and supply scheduling problem (ELSSP) that arises in the distribution and manufacturing industries. The ELSSP involves the simultaneous scheduling of end-item production and inbound transportation of input materials over an infinite time horizon to minimise the average costs of inventory, production set-up and transportation. We present a new methodology based on a time-varying lot sizes approach for the ELSSP. We also provide computational experiments showing that the developed algorithm outperforms the existing heuristic for improved integrated scheduling.     

An agent-based negotiation approach to integrate process planning and scheduling

This paper presents the development of an agent-based negotiation approach to integrate process planning and scheduling (IPPS) in a job shop kind of flexible manufacturing environment. The agent-based system comprises two types of agents, part agents and machine agents, to represent parts and machines respectively. For each part, all feasible manufacturing processes and routings are recorded as alternative process plans. Similarly, alternative machines for an operation are also considered. With regard to the scheduling requirements and the alternative process plans of a part, the proposed agent-based IPPS system aims to specify the process routing and to assign the manufacturing resources effectively. To establish task allocations, the part and machine agents have to engage in bidding. Bids are evaluated in accordance with a currency function which considers an agent's multi-objectives and IPPS parameters. A negotiation protocol is developed for negotiations between the part agents and the machine agents. The protocol is modified from the contract net protocol to cater for the multiple-task and many-to-many negotiations in this paper. An agent-based framework is established to simulate the proposed IPPS approach. Experiments are conducted to evaluate the performance of the proposed system. The performance measures, including makespan and flowtime, are compared with those of a search technique based on a co-evolutionary algorithm.