Flexibility-based multi-objective approach for machines selection in reconfigurable manufacturing system (RMS) design under unavailability constraints

The reconfigurable manufacturing system (RMS) is a recent manufacturing paradigm driven by the high responsiveness and performance efficiencies. In such system, machines, material handling units or machines components can be added, modified, removed or interchanged as needed. Hence, the design of RMS is based on reconfigurable machines capabilities and product specification. This paper addresses the problem of machines selections for RMS design under unavailability constraints and aims to develop an approach to ensure the best process plan according to the customised flexibility required to produce all parts of a given product. More specifically, we develop a flexibility-based multi-objective approach using an adapted version of the well-known non-dominated sorting genetic algorithm to select adequate machines from a set of candidate (potential) ones, in order to ensure the best responsiveness of the designed system in case of unavailability of one of the selected machines. The responsiveness is based on the flexibility of the designed system and a generated process plan, which guarantees the management of machines unavailability. It is defined as the ability and the capacity to adapt the process plan in response to machines unavailability. Two objectives are considered, respectively, the maximisation of the flexibility index of the system and the minimisation of the total completion time. To choose the best solution in the Pareto front, a multi-objective decision-making method called technique for order of preference by similarity to ideal solution is used. To demonstrate the applicability of the proposed approach, a simple example is presented and the numerical results are analysed.     

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.     

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 simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles

In this paper we address the problem of simultaneous scheduling of machines and vehicles in flexible manufacturing systems. The studied problem is a job shop where the jobs have to be transported between the machines by automatic guided vehicles. In addition to the processing of jobs, we consider the transportation aspect as an integral part of the optimization process. To deal with this problem, we propose a new solution representation based on vehicles rather than machines. Each solution can thus be evaluated using a discrete event approach. An efficient neighbouring system is then described and implemented into three different metaheuristics: iterated local search, simulated annealing and their hybridisation. Computational results are presented for a benchmark of 40 literature instances. New upper bounds are found for 11 of them, showing the effectiveness of the presented approach.     

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.     

Material handling considerations in the FMS loading problem with full routing flexibility

This study exploits machining and routing flexibility to effectively deal with the material handling requirements resulting from a frequently changing demand mix in a manufacturing system where material handling is a bottleneck. For this purpose, the objective function of the operation and tool loading problem is selected as the minimisation of the total distance traveled by parts during their production. Versatile machines and the flexible process plans offer full routing flexibility that enable the same workpiece to be processed using alternative sequences of operations on alternative machines. Three mathematical programming (MP) models and a genetic algorithm (GA) are proposed to solve this problem. The proposed MP formulations include a mixed-integer nonlinear programming (MINLP) model and two mixed-integer programming (MIP) models, which offer different representations for the flexible process plans. The GA is integrated with linear programming for fitness evaluation and incorporates several adaptive strategies for diversification. The performances of these solution methods are tested through extensive numerical experiments. The MP models are evaluated on the basis of the exact solutions they yield as well as how they lend themselves for GA fitness evaluation. The GA–LP integration works successfully for this hard-to-solve problem.     

Optimization of process plans using a constraint-based tabu search approach

A computer-aided process planning system should ideally generate and optimize process plans to ensure the application of good manufacturing practices and maintain the consistency of the desired functional specifications of a part during its production processes. Crucial processes, such as selecting machining resources, determining set-up plans and sequencing operations of a part should be considered simultaneously to achieve global optimal solutions. In this paper, these processes are integrated and modelled as a constraint-based optimization problem, and a tabu search-based approach is proposed to solve it effectively. In the optimization model, costs of the utilized machines and cutting tools, machine changes, tool changes, set-ups and departure from good manufacturing practices (penalty function) are the optimization evaluation criteria. Precedence constraints from the geometric and manufacturing interactions between features and their related operations in a part are defined and classified according to their effects on the plan feasibility and processing quality. A hybrid constraint-handling method is developed and embedded in the optimization algorithm to conduct the search efficiently in a large-size constraint-based space. Case studies, which are used for comparing this approach with the genetic algorithm and simulated annealing approaches, and the proposed constraint-handling method and other constraint methods, are discussed to highlight the performance of this approach in terms of the solution quality and computational efficiency of the algorithm.     

A Meta-RaPS for the early/tardy single machine scheduling problem

This paper investigates a meta-heuristic solution approach to the early/tardy single machine scheduling problem with common due date and sequence-dependent setup times. The objective of this problem is to minimise the total amount of earliness and tardiness of jobs that are assigned to a single machine. The popularity of just-in-time (JIT) and lean manufacturing scheduling approaches makes the minimisation of earliness and tardiness important and relevant. In this research the early/tardy problem is solved by Meta-RaPS (meta-heuristic for randomised priority search). Meta-RaPS is an iterative meta-heuristic which is a generic, high level strategy used to modify greedy algorithms based on the insertion of a random element. In this case a greedy heuristic, the shortest adjusted processing time, is modified by Meta-RaPS and the good solutions are improved by a local search algorithm. A comparison with the existing ETP solution procedures using well-known test problems shows Meta-RaPS produces better solutions in terms of percent difference from optimal. The results provide high quality solutions in reasonable computation time, demonstrating the effectiveness of the simple and practical framework of Meta-RaPS.     

An efficient local search heuristic for the double row layout problem with asymmetric material flow

The double row layout problem (DRLP) consists of arranging a number of rectangular machines of varying widths on either side of a corridor to minimize the total cost of material handling for products that move between these machines. This problem arises in the context of many production environments, most notably semiconductor manufacturing. Because the DRLP contains both combinatorial and continuous aspects, traditional solution approaches are not well suited to obtain solutions within a reasonable time. Moreover, previous approaches to this problem did not consider asymmetric flows. In this paper, an effective local search procedure featuring linear programming is proposed for solving the DRLP with asymmetric flows (symmetric flows being a special case). This approach is compared against several constructive heuristics and solutions obtained by a commercial mixed integer linear programming solver to evaluate its performance. Computational results show that the proposed heuristic is an effective approach, both in terms of solution quality and computational effort.     

New heuristics for no-wait flow shops with a linear combination of makespan and maximum lateness

In this work we study a flow shop scheduling problem in which jobs are not allowed to wait between machines, a situation commonly referred to as no-wait. The criterion is to minimise a weighted sum of makespan and maximum lateness. A dominance relation for the case of three machines is presented and evaluated using experimental designs. Several heuristics and local search methods are proposed for the general m-machine case. The local search methods are based on genetic algorithms and iterated greedy procedures. An extensive computational analysis is conducted where it is shown that the proposed methods outperform existing heuristics and metaheuristics in all tested scenarios by a considerable margin and under identical CPU times.     

An improved artificial bee colony algorithm for addressing distributed flow shop with distance coefficient in a prefabricated system

This paper proposes an improved artificial bee colony (IABC) algorithm for addressing the distributed flow shop considering the distance coefficient found in precast concrete production system, with the minimisation of the makespan. In the proposed algorithm, each solution is first represented by a two-dimensional vector, where the first dimensional vector is the factory and the second dimensional vector lists the operation scheduling sequence of each factory. Second, considering the distributed problem feature, a distributed iterated greedy heuristic (DIG) is developed where destruction and construction processes are designed in detail while considering the distributed structures. Third, an efficient population initialisation method that considers the factory workload balance is presented. Then, a local search approach that randomly replaces two factories with two randomly selected jobs and that finds an optimal position for the two inserted operations via the DIG method is proposed. For the canonical ABC algorithm, using the DIG approach, the main three parts are improved, namely, the employee, onlooker, and scout bees. Finally, the proposed algorithm is tested on sets of extended instances based on the well-known benchmarks. Through an analysis of the experimental results, the highly effective proposed IABC algorithm is compared to several efficient algorithms drawn from the literature.     

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.     

A hybrid Hopfield network-genetic algorithm approach to optimal process plan selection

In the automated manufacturing environment, different sets of alternative process plans can normally be generated to manufacture each part. However, this entails considerable complexities in solving the process plan selection problem because each of these process plans demands specification of their individual and varying manufacturing costs and manufacturing resource requirements, such as machines, fixtures/jigs, and cutting tools. In this paper the problem of selecting exactly one representative from a set of alternative process plans for each part is formulated. The purpose is to minimize, for all the parts to be manufactured, the sum of both the costs of the selected process plans and the dissimilarities in their manufacturing resource requirements. The techniques of Hopfield neural network and genetic algorithm are introduced as possible approaches to solve such a problem. In particular, a hybrid Hopfield network-genetic algorithm approach is also proposed in this paper as an effective near-global optimization technique to provide a good quality solution to the process plan selection problem. The effectiveness of the proposed hybrid approach is illustrated by comparing its performance with that of some published approaches and other optimization techniques, by using several examples currently available in the literature, as well as a few randomly generated examples.     

Unrelated parallel machine scheduling with setup times and ready times

We consider the problem of scheduling unrelated parallel machines with sequence- and machine-dependent setup times and ready times to minimise total weighted tardiness (TWT). We present a mixed integer programming model that can find optimal solutions for the studied problem. We also propose a heuristic (ATCSR_Rm) and an iterated hybrid metaheuristic (IHM) that can find optimal or nearly optimal solutions for the studied problem within a reasonable time. The proposed IHM begins with effective initial solutions, and then improves the initial solutions iteratively. The IHM integrates the principles of the attraction–repulsion mechanism within electromagnetism-like algorithms with local search. If the search becomes trapped at a local optimum, an elite search procedure is developed to help the search escape. We have compared our proposed IHM with two existing metaheuristics, tabu search (TS) and ant colony optimisation (ACO). Computational results show that the proposed IHM outperforms TS and ACO in terms of TWT for problem instances of all sizes.     

Solving a multistage partial inspection problem using genetic algorithms

Traditionally, the multistage inspection problem has been formulated as consisting of a decision schedule where some manufacturing stages receive full inspection and the rest none. Dynamic programming and heuristic methods (like local search) are the most commonly used solution techniques. A highly constrained multistage inspection problem is presented where all stages must receive partial rectifying inspection and it is solved using a real-valued genetic algorithm. This solution technique can handle multiple objectives and quality constraints effectively.     

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 multi-level heuristic search algorithm for production scheduling

This paper introduces a multi-level heuristic search algorithm for identifying the optimal production schedule considering different levels of manufacturing requirements and constraints. The multi-level heuristic search algorithm generates search nodes at different levels. An upper level search node is composed of lower level search nodes, and evaluated based upon the evaluation of these lower level search nodes using a heuristic function. A production scheduling system was developed based upon the multi-level heuristic search algorithm. In this scheduling system, production requirements and constraints are represented at three different levels: task level, process level, and resource level. A task describes a manufacturing requirement. A process defines a method to achieve the goal of a task. A resource, such as a machine or a person, is a facility for accomplishing a required process. The multi-level heuristic search-based scheduling system was implemented using Smalltalk, an object-oriented programming language. Discussions on scheduling quality and efficiency are addressed at the end of this paper.     

An integrated approach to solving the process plan selection problem in an automated manufacturing system

Selection of a process plan is a crucial decision making problem encountered in manufacturing systems due to the presence of several alternative process plans arising out of availability of several machines, tools, fixtures etc. capable of performing the same operations of the part. Because of its vital impact on the performance of the manufacturing system, several researchers have addressed the plan selection problem in recent years. Although functional integration plays a significant role in the development of current manufacturing systems, many of the functions in manufacturing systems have been developed without a sense of integration. Therefore, it becomes important to emphasize the integration of functions rather than the individual development of the function itself. This paper attempts to address the plan selection problem taking into account the similarity measures among the process plans of the parts. Four algorithms have been developed to integrate the several segments of the process plan selection problem. Application of these algorithms ensures considerable computational simplicity in yielding the feasible process plans of the parts.     

On-line scheduling of multi-server batch operations

The batching of jobs in a manufacturing system is a very common policy in many industries. The main reasons for batching are the avoidance of setups and/or facilitation of material handling. Good examples of batch-wise production systems are the ovens that are found in the aircraft industry and in the manufacture of semiconductors. These systems often consist of multiple machines of different types for the range and volumes of products that have to be handled. Building on earlier research in the aircraft industry, where the process of hardening synthetic aircraft parts was studied, we propose a new heuristic for the dynamic scheduling of these types of systems. Our so-called look-ahead strategy bases its decision to schedule a job on a certain machine on the availability of information on a limited number of near future arrivals. The new control strategy distinguishes itself from existing heuristics by an integrated approach that involves all machines in the scheduling decision, instead of only considering idle machines. It is shown by an extensive series of simulation experiments that the new heuristic outperforms existing heuristics for most system configurations. Especially in the case of complex systems, where multiple products have to be handled by non-identical machines, the new heuristic proves its value as a practical scheduling tool. Important insight is obtained with regard to the relation between the system is configuration and its performance.     

Scheduling identical wafer sorting parallel machines with sequence-dependent setup times using an iterated greedy heuristic

Wafer sorting is one of the most critical processes involved in semiconductor device fabrication. This study addresses the wafer sorting scheduling problem (WSSP), with minimisation of total setup time as the primary criterion and minimisation of the number of testers used as the secondary criterion. In view of the strongly NP-hard nature of this problem, a simple and effective iterated greedy heuristic is presented. The performance of the proposed heuristic is empirically evaluated by 480 simulation instances based on the characteristics of a real wafer testing shop-floor. The experimental results show that the proposed heuristic is effective and efficient as compared to the state-of-art algorithms developed for the same problem. It is believed that this study has developed an approach that is easy to comprehend and satisfies the practical needs of wafer sorting.