An improved imperialist competitive algorithm based photolithography machines scheduling

Abstract: Photolithography machine is one of the most expensive equipment in semiconductor manufacturing system, and as such is often the bottleneck for processing wafers. This paper focuses on photolithography machines scheduling with the objective of total completion time minimisation. In contrast to classic parallel machines scheduling, it is characterised by dynamical arrival wafers, re-entrant process flows, dedicated machine constraints and auxiliary resources constraints. We propose an improved imperialist competitive algorithm (ICA) within the framework of a rolling horizon strategy for the problem. We develop a variable time interval-based rolling horizon strategy to decide the scheduling point. We address the global optimisation in every local scheduling by proposing a mixed cost function. Moreover, an adaptive assimilation operator and a sociopolitical competition operator are used to prevent premature convergence of ICA to local optima. A chaotic sequence-based local search method is presented to accelerate the rate of convergence. Computational experiments are carried out comparing the proposed algorithm with ILOG CPLEX, dispatching rules and meta-heuristic algorithms in the literature. It is observed that the algorithm proposed shows an excellent behaviour on cycle time minimisation while with a good on time delivery rate and machine utilisation rate.     

A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flowshop problem

This paper deals with the two-stage assembly flowshop scheduling problem with minimisation of weighted sum of makespan and mean completion time as the objective. The problem is NP-hard, hence we proposed a meta-heuristic named imperialist competitive algorithm (ICA) to solve it. Since appropriate design of the parameters has a significant impact on the algorithm efficiency, we calibrate the parameters of this algorithm using the Taguchi method. In comparison with the best algorithm proposed previously, the ICA indicates an improvement. The results have been confirmed statistically.     

Minimising earliness and tardiness penalties in single machine scheduling against common due date using imperialist competitive algorithm

In this paper a novel evolutionary-based approach is utilised for efficiently solving the NP-hard problem of scheduling numerous common-due-date jobs on a single machine. Minimising the sum of earliness and tardiness penalties for all jobs is considered as the target function. The performance of the proposed approach is examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs where the numerical results indicate that it can produce ‘better’ solutions in less computational time when compared to benchmark results and the methods available in the literature, namely genetic algorithm (GA), Tabu search (TS) and differential evolution (DE).     

Group scheduling in flexible flow shops: a hybridised approach of imperialist competitive algorithm and electromagnetic-like mechanism

This paper applied a novel evolutionary algorithm, imperialist competitive algorithm (ICA), for a group scheduling problem in a hybrid flexible flow shop with sequence-dependent setup times by minimising maximum completion time. This algorithm simulates a social-economical procedure, imperialistic competition. Initial population is generated randomly and evolution is carried out during the algorithm. Firstly individuals, countries, are divided into two categories: imperialists and colonies. Imperialist competition will occur among these empires. This competition will increase some empires authority by ruining a weak empire and dividing its colonies among others. Electromagnetic-like mechanism concepts are employed here to model the influence of the imperialist on their colonies. The algorithm will continue until one imperialist exists and possesses all countries. In order to prevent carrying out extensive experiments to find optimum parameters of the algorithm, we apply the Taguchi approach. The computational results are compared with the outstanding benchmark on the flow shop scheduling problem, random key genetic algorithms (RKGA), and it shows superiority of the ICA.     

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.     

An efficient imperialist competitive algorithm for scheduling in the two-stage assembly flow shop problem

This paper considers a two-stage assembly flow shop problem where m parallel machines are in the first stage and an assembly machine is in the second stage. The objective is to minimise a weighted sum of makespan and mean completion time for n available jobs. As this problem is proven to be NP-hard, therefore, we employed an imperialist competitive algorithm (ICA) as solution approach. In the past literature, Torabzadeh and Zandieh (2010 Torabzadeh, E., and M. Zandieh. 2010. “Cloud theory-based Simulated Annealing Approach for Scheduling in the Two-stage Assembly Flow Shop.” Advances in Engineering Software 41: 1238–1243.[Crossref], [Web of Science ®] , [Google Scholar]) showed that cloud theory-based simulated annealing algorithm (CSA) is an appropriate meta-heuristic to solve the problem. Thus, to justify the claim for ICA capability, we compare our proposed ICA with the reported CSA. A new parameters tuning tool, neural network, for ICA is also introduced. The computational results clarify that ICA performs better than CSA in quality of solutions.     

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.     

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.     

Integrated process planning and scheduling for large-scale flexible job shops using metaheuristics

In this paper, we discuss an integrated process planning and scheduling problem in large-scale flexible job shops (FJSs). We assume that products can be manufactured in different ways, i.e. using different bills of materials (BOM) and routes for the same product. The total weighted tardiness is the performance measure of interest. A Mixed Integer Programming formulation is provided for the researched problem. Because of the NP-hardness of the investigated problem, an iterative scheme is designed that is based on variable neighbourhood search (VNS) on the process planning level. Appropriate neighbourhood structures for VNS are proposed. Because the evaluation of each move within VNS requires the solution of a large-scale FJS scheduling problem instance, efficient heuristics based on local search from previous research are considered on the scheduling level. Extensive computational experiments based on new randomly generated problem instances are conducted. In addition, a parallel version of the VNS is investigated within the computational experiments. The proposed iterative scheme is benchmarked against a genetic algorithm (GA) from the literature that simultaneously considers process planning and scheduling for the special case where a single BOM is available for each product. It turns out that the new iterative scheme outperforms the GA and a memetic algorithm based on the GA. It is able to solve even large-size problem instances in reasonable amount of time.     

Optimizing water supply and hydropower reservoir operation rule curves: An imperialist competitive algorithm approach

Efficient reservoir management requires the implementation of generalized optimal operating policies that manage storage volumes and releases while optimizing a single objective or multiple objectives. Reservoir operating rules stipulate the actions that should be taken under the current state of the system. This study develops a set of piecewise linear operating rule curves for water supply and hydropower reservoirs, employing an imperialist competitive algorithm in a parameterization–simulation–optimization approach. The adaptive penalty method is used for constraint handling and proved to work efficiently in the proposed scheme. Its performance is tested deriving an operation rule for the Dez reservoir in Iran. The proposed modelling scheme converged to near-optimal solutions efficiently in the case examples. It was shown that the proposed optimum piecewise linear rule may perform quite well in reservoir operation optimization as the operating period extends from very short to fairly long periods.     

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.     

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.     

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.     

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.     

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.     

Remanufacturing-oriented process planning and scheduling: mathematical modelling and evolutionary optimisation

Remanufacturing has been widely studied for its potential to achieve sustainable production in recent years. In the literature of remanufacturing research, process planning and scheduling are typically treated as two independent parts. However, these two parts are in fact interrelated and often interact with each other. Doing process planning without considering scheduling related factors can easily introduce contradictions or even infeasible solutions. In this work, we propose a mathematical model of integrated process planning and scheduling for remanufacturing (IPPSR), which simultaneously considers the process planning and scheduling problems. An effective hybrid multi-objective evolutionary algorithm (HMEA) is presented to solve the proposed IPPSR. For the HMEA, a multidimensional encoding operator is designed to get a high-quality initial population. A multidimensional crossover operator and a multidimensional mutation operator are also proposed to improve the convergence speed of the algorithm and fully exploit the solution space. Finally, a specific legalising method is used to ‘legalise’ possible infeasible solutions generated by the initialisation method and mutation operator. Extensive computational experiments carried out to compare the HMEA with some well-known algorithms confirm that the proposed HMEA is able to obtain more and better Pareto solutions for IPPSR.     

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.     

Integrated scheduling of rake and stockyard management with ship berthing: a block based evolutionary algorithm

An integrated problem of optimising the operations at a commercial bulk material port terminal is studied in this paper. We simultaneously optimise the stockyard operations and rake schedule for outbound cargo, in conjunction with the arriving vessels and the status of the stockyards at the port. A mixed integer linear programming model for the problem is developed while incorporating the inherent complexities of the integrated model. To solve the real-life instances, two heuristic methods are proposed specifically for the considered problem. Firstly, genetic algorithm coupled with a greedy heuristic and later, block-based evolutionary algorithm (BBEA) is employed. After applying both techniques, we obtain the optimised schedule for loading of rakes and allotment of stockyard space for vessels as well as rakes at the terminal. Finally, we test the results of both models in three traffic scenarios between themselves and with real-life data from a port situated along the Eastern coast of India. The study resulted in significant reduction of turnaround time for rakes at the port terminal, which in turn lead to monetary savings. The model also automates the day to day operational decision-making at the port.     

A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem

This article addresses the distributed two-stage assembly flow-shop scheduling problem (DTSAFSP) with makespan minimisation criterion. A mixed integer linear programming model is presented, and a competitive memetic algorithm (CMA) is proposed. When designing the CMA, a simple encoding scheme is proposed to represent the factory assignment and the job processing sequence; and a ring-based neighbourhood structure is designed for competition and information sharing. Moreover, some knowledge-based local search operators are developed to enhance the exploitation ability. The influence of parameter setting on the CMA is investigated using the analysis of variance method. Extensive computational tests and comparisons are carried out, which demonstrate the effectiveness of the proposed CMA in solving the DTSAFSP.