Multi-objective multi-unit process plan generation in a reconfigurable manufacturing environment: a comparative study of three hybrid metaheuristics

Low costs, high reactivity and high quality products are necessary criteria for industries to achieve competitiveness in nowadays market. In this context, reconfigurable manufacturing systems (RMSs) have emerged to fulfil these requirements. RMS is one of the latest manufacturing paradigms, where machines components, software or material handling units can be added, removed, modified or interchanged as needed and when imposed by the necessity to react and respond rapidly and cost-effectively to changing. This research work addresses the multi-objective single-product multi-unit process plan generation problem in a reconfigurable manufacturing environment where three hybrid heuristics are proposed and compared namely: repetitive single-unit process plan heuristic (RSUPP), iterated local search on single-unit process plans heuristic (LSSUPP) and archive-based iterated local search heuristic (ABILS). Single-unit process plans are generated using the adapted non-dominated sorting genetic algorithm (NSGA-II). Moreover, in addition to the minimisation of the classical total production cost and the total completion time, the minimisation of the maximum machines exploitation time is considered as a novel optimisation criterion, in order to have high quality products. To illustrate the applicability of the three approaches, examples are presented and the obtained numerical results are analysed.     

Minimising total completion time on single-machine scheduling with new integrated maintenance activities

A single-machine scheduling problem with new maintenance activities is examined in this paper. In the scheduling literature, it is often assumed that the interval between maintenance activities is fixed or within a specified time frame. However, this assumption may not hold true in many real-world situations, such as the maintenance activities in wafer manufacturing of semiconductor. Before the wafer manufacturing process starts, it is imperative that the wafers go through a number of cleaning operations to avoid contamination. Using a cleaning agent as the main material of wafer cleaning, the contamination will be dissolved and removed from wafer surface. In case of contamination being accumulated substantial and going beyond a permitted value, the cleaning agent is highly likely to damage the wafer surfaces. Thus, the interval between maintenance activities in the wafer manufacturing process is deemed irregular. The objective function of the proposed problem is to minimise total completion time. Addressing the problem, a binary integer programming model is formulated in this paper. Furthermore, with the research problem being NP-hard, a heuristic based on two special properties is proposed to address the problem. To evaluate and validate the proposed heuristic, a new lower bound is further developed. Extensive experiments have been conducted showing that the proposed heuristic efficiently yields a near-optimal solution with an average percentage error of 15.4 from lower bound.     

Green permutation flowshop scheduling problem with sequence-dependent setup times: a case study

Increasing global energy consumption, large variations in its cost and the environmental degradation effects are good reasons for the manufacturing industries to become greener. Green shop floor scheduling is increasingly becoming a vital factor in the sustainable manufacturing. In this paper, a green permutation flowshop scheduling problem with sequence-dependent setup times is studied. Two objectives are considered including minimisation of makespan as a measure of service level and minimisation of total energy consumption as a measure of environmental sustainability. We extend a bi-objective mixed-integer linear programming model to formulate the stated problem. We develop a constructive heuristic algorithm to solve the model. The constructive heuristic algorithm includes iterated greedy (CHIG) and local search (CHLS) algorithms. We develop an efficient energy-saving method which decreases energy consumption, on average, by about 15%. To evaluate the effectiveness of the constructive heuristic algorithm, we compare it with the famous augmented ?-constraint method using various small-sized and large-sized problems. The results confirm that the heuristic algorithm obtains high-quality non-dominated solutions in comparison with the augmented ?-constraint method. Also, they show that the CHIG outperforms the CHLS. Finally, this paper follows a case-study, with in-depth analysis of the model and the constructive heuristic algorithm.     

Multi-threaded simulated annealing for a bi-objective maintenance scheduling problem

A parallel Simulated Annealing algorithm with multi-threaded architecture is proposed to solve a real bi-objective maintenance scheduling problem with conflicting objectives: the minimisation of the total equipment downtime caused by maintenance jobs and the minimisation of the multi-skilled workforce requirements over the given horizon. The maintenance jobs have different priorities with some precedence relations between different skills. The total weighted flow time is used as a scheduling criterion to measure the equipment availability. The multi-threaded architecture is used to speed up a multi-objective Simulated Annealing algorithm to solve the considered problem. Multi-threading is a form of parallelism based on shared memory architecture where multiple logical processing units, so-called threads, run concurrently and communicate via shared memory. The performance of the parallel method compared to the exact method is verified using a number of test problems. The obtained results imply the high efficiency and robustness of the proposed heuristic for both solution quality and computational effort.     

Single-machine scheduling problems with a batch-dependent aging effect and variable maintenance activities

We consider single-machine scheduling problems with a batch-dependent ageing effect and variable maintenance activities between batches. The machine can process several jobs as a batch. It requires maintenance activities where the maintenance time depends on the flow time of the pre-batch, i.e. the batch processed before a batch. A job’s actual processing time is an increasing exponential function of its operation time within a batch. The objectives are to minimise the makespan and the total completion time. We develop polynomial time algorithms for the makespan minimisation problem and the total completion time minimisation problem under the condition that the ageing factor is greater than one. We also provide a mathematical programming approach and two heuristic algorithms to analyse the total completion time minimisation problem when the ageing factor is less than one for even one batch. The computational analysis indicates that the proposed heuristic algorithms are more efficient for the smaller ageing factor, whereas the Modified Shortest Processing Time algorithm is more efficient than the proposed heuristic algorithms for the larger ageing factor.     

A tabu search algorithm for solving a multicriteria flexible job shop scheduling problem

The problem that we consider in this article is a flexible job shop scheduling problem issued from the printing and boarding industry. Two criteria have to be minimised, the makespan and the maximum lateness. Two tabu search algorithms are proposed for finding a set of non-dominated solutions: the first is based on the minimisation of one criterion subject to a bound on the second criterion (ε-constraint approach) and the second is based on the minimisation of a linear combination of criteria. These algorithms are tested on benchmark instances from the literature and the results are discussed. The total tardiness is considered as a third criterion for the second tabu search and results are presented and discussed.     

Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times

This paper studies the makespan minimisation scheduling problem in a two-stage hybrid flow shop. The first stage has one machine and the second stage has m identical parallel machines. Neither the processing time nor probability distribution of the processing time of each job is uncertain. We propose a robust (min–max regret) scheduling model. To solve the robust scheduling problem, which is NP-hard, we first derive some properties of the worst-case scenario for a given schedule. We then propose both exact and heuristic algorithms to solve this problem. In addition, computational experiments are conducted to evaluate the performance of the proposed algorithms.     

Scheduling multistage hybrid flowshops with multiprocessor tasks by an effective heuristic

This study considers the scheduling problem of multistage hybrid flowshops with multiprocessor tasks, which is a core topic for numerous industrial applications. An effective and efficient heuristic, namely the heuristic of multistage hybrid flowshops (HMHF) is proposed to solve this problem. To verify the developed heuristic, computational experiments are conducted on a well-known benchmark problem set. The results are compared with 10 constructive heuristics and a tabu search (TS) based meta-heuristic from the relevant literature. These computational results show that the proposed HMHF heuristic is highly effective when compared to these algorithms for this problem on the same benchmark instances.     

Simultaneous order-lot pegging and wafer release planning for semiconductor wafer fabrication facilities

In semiconductor wafer fabrication facilities, order-lot pegging is the process of assigning wafer lots to orders and meeting the due dates of orders is considered one of the most important operational issues. In many cases of order-lot pegging, some orders cannot be fulfilled with the current wafers in the lots being processed, necessitating the release of additional new wafer lots into the wafer fabrication facility. In this paper, we propose a simultaneous decision model for order-lot pegging and wafer release planning in semiconductor wafer fabrication facilities, and develop a Lagrangian heuristic for solving the model. The results of computational experiments conducted using randomly generated problem instances that mimic actual field data from a Korea semiconductor wafer fabrication facility indicate that the performance of the Lagrangian heuristic is superior to that of a practical greedy algorithm for practical-sized problem instances. The results also point to how sensitivity analysis can be used to answer important managerial questions for effective management of the semiconductor wafer fabrication process.     

Solving the blocking flow shop scheduling problem with makespan using a modified fruit fly optimisation algorithm

The flow shop scheduling problem with blocking has important applications in a variety of industrial systems but is under-represented in the research literature. In this paper, a modified fruit fly optimisation (MFFO) algorithm is proposed to solve the above scheduling problem for makespan minimisation. The MFFO algorithm mainly contains three key operators. One is related to the initialisation scheme in which a problem-specific heuristic is adopted to generate an initial fruit fly swarm location with high quality. The second is concerned with the smell-based search in which a neighbourhood strategy is designed to generate a new location. To further enhance the exploitation of the proposed algorithm considered, a speed-up insert-neighbourhood-based local search is applied with a probability. Finally, the last is for the vision-based search in which an update criterion is proposed to induce the fruit fly into a better searching space. The simulation experimental results demonstrated the efficiency of the proposed algorithm, in spite of its simple structure, in comparison with a state-of-the-art algorithm. Moreover, new best solutions for Taillard’s instances are reported for this problem, which can be used as a basis of comparison in future studies.     

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.     

API-based two-dimensional dispatching decision-making approach for semiconductor wafer fabrication with operation due date–related objectives

This paper presents an adjacent pairwise interchanges (API)-based two-dimensional dispatching decision-making approach for semiconductor wafer fabrication with operation due date-related objectives. Each time when a machine becomes idle, the proposed dispatcher chooses a target processing job from the competing jobs and assigns it a start time. Giving the operation due date information of each competing job, we formulate this dispatcher as the mean absolute deviation problem to keep the jobs finished around their operation due dates in a proactive way. Dominance properties of this problem are established using proof by APIs. Then, a heuristic comprised of job selection within candidate set, movement of job cluster and local search is designed to solve this problem more efficiently. Numerical experiments validate the efficiency of the proposed heuristic in a single-machine environment as well as in a simulated wafer fab abstracted from practice. In comparison with four most referenced due date-related dispatching rules, the simulation study reveals the benefits brought by the two-dimensional dispatching decision with different due date tightness taken into account.     

Improved imperialist competitive algorithms for rebalancing multi-objective two-sided assembly lines with space and resource constraints

In this paper, a mathematical model and an improved imperial competition algorithm (IICA) are proposed to solve the multi-objective two-sided assembly line rebalancing problem with space and resource restrictions (MTALRBP-SR). The aim is to find lines’ rebalance with the trade-off between efficiency, rebalancing cost and smoothing after reconfiguration. IICA utilises a new initialisation heuristic procedure based on classic heuristic rules to generate feasible initial solutions. A novel heuristic assimilation method is developed to vigorously conduct local search. In addition, a group-based decoding heuristic procedure is developed to fulfil the final task reassignment with the additional restrictions. To investigate the performance of the proposed algorithm, it is first tested on MTALRBP of benchmark problems and compared with some existing algorithms such as genetic algorithm, variable neighbourhood search algorithm, discrete artificial bee colony algorithm, and two iterated greedy algorithms. Next, the efficiency of the proposed IICA for solving MTALRBP-SR is revealed by comparison with a non-dominated sorting genetic algorithm (NSGA-II) and two versions of original ICA. Computational results and comparisons show the efficiency and effectiveness of IICA. Furthermore, a real-world case study is conducted to validate the proposed algorithm.     

Fuzzy bi-objective formulation for a parallel machine scheduling problem with machine eligibility restrictions and sequence-dependent setup times

In this paper, a fuzzy bi-objective mixed-integer linear programming (FBOMILP) model is presented. FBOMILP encompasses the minimisation workload imbalance and total tardiness simultaneously as a bi-objective formulation for an unrelated parallel machine scheduling problem. To make the proposed model more practical, sequence-dependent setup times, machine eligibility restrictions and release dates are also considered. Moreover, the inherent uncertainty of processing times, release dates, setup times and due dates are taken into account and modelled by fuzzy numbers. In order to solve the model for small-scale problems, a two-stage fuzzy approach is proposed. Nevertheless, since the problem belongs to the class of NP-hard problems, the proposed model is solved by two meta-heuristic algorithms, namely fuzzy multi-objective particle swarm optimisation (FMOPSO) and fuzzy non-dominated sorting genetic algorithm (FNSGA-II) for solving large-scale instances. Subsequently, through setting up various numerical examples, the performances of the two mentioned algorithms are compared. When α?=?0.5 (α is a level of risk-taking and when it increases the decision-maker’s risk-taking decreases), FNSGA-II is fairly more effective than FMOPSO and has better performance especially in solving large-sized problems. However, when α rises, it can be stated that FMOPSO moderately becomes more appropriate. Finally, directions for future studies are suggested and conclusion remarks are drawn.     

Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint

This study considers a single machine group scheduling problem with deteriorating jobs and resource allocation (controllable processing times). The objective is to have the resource availability limited within a given range, and to minimize the maximum completion time (i.e. the makespan). For two special cases, it is proved that the problem can be solved in polynomial time. For the general case, an heuristic algorithm and a branch-and-bound algorithm are proposed. Computational results show that the proposed heuristic algorithm is generally effective.     

Heuristic algorithms to solve the capacity allocation problem in photolithography area (CAPPA)

Wafer fabrication is one of the most complex and high competence manufacturing. How to fully utilize the machine capacity to meet customer demand is a very important topic. In this paper, we address the capacity allocation problem for photolithography area (CAPPA), which belongs to a capacity requirement planning scheme, with the process window and machine dedication restrictions that arise from an advanced wafer fabrication technology environment. Process window means that a wafer needs to be processed on machines that can satisfy its process capability (process specification). Machine dedication means that once the first critical layer of a wafer lot is processed on a certain machine, the subsequent critical layers of this lot must be processed on the same machine to ensure good quality of final products. We present six modified heuristics and a linear-programming-based heuristic algorithm (LPBHA) to solve the problem efficiently. The performance of the proposed algorithms is tested using real-world CAPPA cases taken from wafer fabrication photolithography area. Computational results show that LPBHA is the most effective one, and with a least average and a least standard deviation of deviation ratio of 0.294 and 0.085% compared to the lower bound of the CAPPA.     

Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach

The hybrid flow-shop scheduling problem (HFSP) has been of continuing interest for researchers and practitioners since its advent. This paper considers the multistage HFSP with multiprocessor tasks, a core topic for numerous industrial applications. A novel ant colony system (ACS) heuristic is proposed to solve the problem. To verify the developed heuristic, computational experiments are conducted on two well-known benchmark problem sets and the results are compared with genetic algorithm (GA) and tabu search (TS) from the relevant literature. Computational results demonstrate that the proposed ACS heuristic outperforms the existing GA and TS algorithms for the current problem. Since the proposed ACS heuristic is comprehensible and effective, this study successfully develops a near-optimal approach which will hopefully encourage practitioners to apply it to real-world problems.     

A dynamic scheduling algorithm for singe-arm two-cluster tools with flexible processing times

This article presents a dynamic algorithm for job scheduling in two-cluster tools producing multi-type wafers with flexible processing times. Flexible processing times mean that the actual times for processing wafers should be within given time intervals. The objective of the work is to minimize the completion time of the newly inserted wafer. To deal with this issue, a two-cluster tool is decomposed into three reduced single-cluster tools (RCTs) in a series based on a decomposition approach proposed in this article. For each single-cluster tool, a dynamic scheduling algorithm based on temporal constraints is developed to schedule the newly inserted wafer. Three experiments have been carried out to test the dynamic scheduling algorithm proposed, comparing with the results the ‘earliest starting time’ heuristic (EST) adopted in previous literature. The results show that the dynamic algorithm proposed in this article is effective and practical.     

Robust single machine scheduling with uncertain release times for minimising the maximum waiting time

We study a single machine scheduling problem (SMSP) with uncertain job release times (JRTs) under the maximum waiting time (MWT) criterion. To deal with the uncertainty, a robust model is established to find an optimal schedule, which minimises the worst-case MWT (W-MWT) when JRTs vary over given time intervals. Although infinite possible scenarios for JRTs exist, we show that only n scenarios are needed for calculating the W-MWT, where n is the number of jobs. Based on this property, the robust (SMSP) with uncertain JRTs to minimise the W-MWT is formulated as a mixed integer linear programming problem. To solve large-size problem instances, an efficient two-stage heuristic (TSH) is proposed. In the first stage, n near-optimal schedules are obtained by solving n deterministic scenario-based SMSPs, and their W-MWTs are evaluated. To speed up the solution and evaluation process, a modified Gusfield’s heuristic is proposed by exploiting the inner connections of these SMSPs. To further improve the schedule obtained in the first stage, the second stage consists of a variable neighbourhood search method by combining both swap neighbourhood search and insert neighbourhood search. We also develop a method to calculate the lower bound of the proposed model so that we can evaluate the performance of the solutions given by the TSH. Experimental results confirm the robustness of schedules produced and advantages of the proposed TSH over other algorithms in terms of solution quality and run time.     

A multi-objective iterated greedy search for flowshop scheduling with makespan and flowtime criteria

In this paper, we tackle the problem of total flowtime and makespan minimisation in a permutation flowshop. For this, we introduce a multi-criteria iterated greedy search algorithm. This algorithm iterates over a multicriteria constructive heuristic approach to yield a set of Pareto-efficient solutions (a posteriori approach). The proposed algorithm is compared against the best-so-far heuristic for the problem under consideration. The comparison shows the proposal to be very efficient for a wide number of multicriteria performance measures. Aside, an extensive computational experience is carried out in order to analyse the different parameters of the algorithm. The analysis shows the algorithm to be robust for most of the considered performance measures.