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.     

Bid generation and evaluation for MANPro-based real time scheduling

This paper proposes a bid generation and evaluation scheme and an information model for real-time scheduling. It is well known that an agent-based control approach performs according to both the negotiation mechanism itself and the single agent internal strategic policies. Mobile agent-based negotiation process (MANPro), which has been proposed in our previous work, concerns the first issue of the negotiation mechanism. This paper concerns the second issue of the single agent internal strategic policies. It explains how bids are generated and evaluated and how agents obtain mutual agreement in MANPro. First, the generic bid generation and evaluation framework for MANPro-based negotiation is proposed. Then, the generic framework is applied to a real-time scheduling system for a distributed shop floor control system (SFCS).     

A priority scheduling approach for flexible job shops with multiple process plans

This paper considers the job shop scheduling problem with alternative operations and machines, called the flexible job shop scheduling problem. As an extension of previous studies, operation and routing flexibilities are considered at the same time in the form of multiple process plans, i.e. each job can be processed through alternative operations, each of which can be processed on alternative machines. The main decisions are: (a) selecting operation/machine pair; and (b) sequencing the jobs assigned to each machine. Since the problem is highly complicated, we suggest a practical priority scheduling approach in which the two decisions are done at the same time using a combination of operation/machine selection and job sequencing rules. The performance measures used are minimising makespan, total flow time, mean tardiness, the number of tardy jobs, and the maximum tardiness. To compare the performances of various rule combinations, simulation experiments were done on the data for hybrid systems with an advanced reconfigurable manufacturing system and a conventional legacy system, and the results are reported.     

Conflict detection and resolution for goal formation in the fractal manufacturing system

The fractal manufacturing system (FrMS) is based on the concept of autonomously cooperating agents referred to as fractals. A fractal is a set of self-similar agents whose goal can be achieved through cooperation, coordination, and negotiation among the agents for themselves. A fractal has fractal-specific characteristics (e.g. self-similarity, self-organization, self-optimization, goal-orientation, and dynamics), and it also has the characteristics of an agent (e.g. autonomy, mobility, intelligence, cooperation, and adaptability) at the same time. In the FrMS, a goal can be regarded as the status which the system aspires to be in. The goal-formation process (GFP) in the FrMS is a process of generating goals and modifying them by coordination between agents. In the GFP, conflicts may occur between goals, which can drive a system to become inefficient. In this paper, a conflict resolution mechanism via agent-based negotiation is proposed for facilitating the GFP. The scheme deals with non-fixed goals. The mobile agent-based negotiation process (MANPro), in which a mobile agent is used for information-exchanging and problem-solving, is used for negotiations in this scheme. The proposed mechanism is illustrated with a goal formation scenario in an exemplary FrMS.     

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.     

Integrated design of cellular manufacturing systems in the presence of alternative process plans

In this paper we consider a generalized group technology problem of manufacturing a group of parts in which each part can have alternative process plans and each operation in these plans can be performed on alternative machines. The objective is to model and analyse how alternative process plans influence the resource utilization when the part families and machine groups are formed simultaneously. Accordingly, we develop three integer programming models to successively study the effect of alternative process plans and simultaneous formation of part families and machine groups. An illustrative example is included.     

MANPro: mobile agent-based negotiation process for distributed intelligent manufacturing

This paper examines negotiation procedures in an agent-based distributed shop floor control system (SFCS). A distributed SFCS is under a heterogeneous environment, which is controlled through negotiations between autonomous agents. The negotiation-based control can be considered as the core of a distributed control paradigm. An efficient information exchanging mechanism and an information model with reasonable structure are indispensable for effective negotiations. This paper proposes a novel negotiation mechanism, called a mobile agent-based negotiation process (MANPro), which applies a mobile agent system to the process of information exchange. Since using mobile agents allows each component to execute asynchronously and autonomously and to adapt dynamically to the execution environment, MANPro may guarantee autonomy of agents. Moreover, it is possible to build a fully distributed and autonomous SFCS by using MANPro. MANPro is based on the agent-based control architecture, which includes a communication architecture and an information architecture. The communication architecture provides the exchanging mechanism of information, defining functional modules to support the mechanism while the information architecture provides the framework for information modelling on negotiation, proposing information models required for introducing the ontology concept.     

Design and scheduling of hybridmulti-cell flexible manufacturing systems

The objective of this paper is to minimize machine duplication by increasing its utilization, minimize intercell moves, simplify the scheduling problem and increase the flexibility of the manufacturing system. An integrated approach of design and scheduling alternative hybrid multi-cell flexible manufacturing systems (MCFMSs) in four steps will be presented in this paper. The first step is the implementation of branch and bound techniques which provide tools to design group technology (GT) cells. The second step is balancing the inter-cell workload of GT cells which leads to a hybrid MCFMS with better utilization of the machines. The problem of the exception machines and their utilization and workload balance will be solved within the MCFMScentre. Thus the performance of GT cells can be improved by transferring workloads from a congested (bottleneck) machine in one cell to an alternative one, a less congested (exception) machine in another cell within a group of GT cells forming a MCFMS centre. The third step is the group scheduling; a proposed heuristic method will be used for the scheduling of a family of parts with the objective of minimizing the maximum completion time of each part. The problem of scheduling under MCFMS can be reduced by considering the scheduling of each family of parts. Finally, the flexibility of the system will be enhanced by selecting appropriate machine tools and flexible material handling equipments. This approach is both effective and efficient-it has generated a hybrid MCFMS centre which includes several alternatives, for some benchmark problems in much shorter time than algorithms previously reported in the literature. In addition, the method is conceptually simple and easy to implement.     

Cell design and multi-period machine loading in cellular reconfigurable manufacturing systems with alternative routing

This paper deals with the design and loading of Cellular Reconfigurable Manufacturing Systems in the presence of alternative routing and multiple time periods. These systems consist of multiple reconfigurable machining cells, each of which has Reconfigurable Machine Tools and Computer Numerical Control (CNC) machines. Each reconfigurable machine has a library of feasible auxiliary machine modules for achieving particular operational capabilities, while each CNC machine has an automatic tool changer and a tool magazine of a limited capacity. The proposed approach consists of two phases: the machine cell design phase which involves the grouping of machines into machine cells, and the cell loading phase that determines the routing mix and the tool and module allocation. In this paper, the cell design problem is modelled as an Integer Linear Programming formulation, considering the multiple process plans of each part type as if they were separate part types. Once the manufacturing cells are formed, a Mixed Integer Linear Programming model is developed for the cell loading problem, considering multi-period demands for the part types, and minimising transportation and holding costs while keeping the machine and cell utilisations in each period, and the system utilisation across periods, approximately balanced. An illustrative problem and experimental results are presented.     

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.     

Flexible job-shop scheduling/rescheduling in dynamic environment: a hybrid MAS/ACO approach

In real-world manufacturing, disruptions are often encountered during the execution of a predetermined schedule, leading to the degradation of its optimality and feasibility. This study presents a hybrid approach for flexible job-shop scheduling/rescheduling problems under dynamic environment. The approach, coined as ‘HMA’ is a combination of multi-agent system (MAS) negotiation and ant colony optimisation (ACO). A fully distributed MAS structure has been constructed to support the solution-finding process by negotiation among the agents. The features of ACO are introduced into the negotiation mechanism in order to improve the performance of the schedule. Experimental studies have been carried out to evaluate the performance of the approach for scheduling and rescheduling under different types of disruptions. Different rescheduling policies are compared and discussed. The results have shown that the proposed approach is a competitive method for flexible job-shop scheduling/rescheduling for both schedule optimality and computation efficiency.     

Distributed intelligent control of exceptions in reconfigurable manufacturing systems

In order to react to the continuous and unpredictable changes in product demand, in product variety, and in process technologies, reconfigurable manufacturing systems allow quick adjustment of production capacity and functionality by rearranging or changing their modular components. In this kind of system, operation management issues, such as exception handling policies, become more complex since correct reconfiguration strategies have to be selected. This paper explores the potential of the reconfigurability feature to be a basis for the development of new strategies to handle out-of-the-ordinary events in the production process; in particular, maintaining production flow when machine breakdowns occur. Decisions regarding how to deal with exceptions to the production process are complex and depend on the manufacturing system configuration and on many performance and economic variables. The authors propose agent-based manufacturing control for exception handling because of its ability to be very agile, as well as being reactive and efficient. Manufacturing agents, while working to pursue their specific goals, achieve the global target of the system. Complex decisions can be made due to the synergy arising from the agents' internal reasoning and the negotiation process among these agents. The adopted negotiation mechanism is based on the contract-net protocol, while different strategies have been designed for the internal reasoning. The authors demonstrate that, under certain conditions, an agent's internal strategies based on fuzzy reasoning improve the global performance of the system. The proposed control model has been tested on a discrete event simulation test-bed.     

Development of a hybrid negotiation scheme for multi-agent manufacturing systems

A hybrid inter-agent negotiation mechanism based on currency and a pre-emption control scheme is proposed to improve the performance of multi-agent manufacturing systems. The multi-agent system considered consists mainly of four types of agents: machine, clone, part and mediator. The machine agent controls the scheduling and the execution of a task. The clone agent aims to maximize the utilization rate by attracting relevant work to the machine. The part agent communicates with the machine agent or clone agent to acquire necessary production resources in order to get the required processing done, and the mediator agent contains the status of the part that will be processed by the subcontracting machine agent. The primary objective is to design decentralized control protocols for discrete part manufacturing systems to enhance the efficiency of the system and to allocate dynamically the resources to critical jobs based on the dynamic search tree. This research incorporates both the currency and the pre-emption schemes within a common framework. Currency functions are used to help the agents meet their individual objectives, whereas the pre-emption scheme is used to expedite the processing of parts based on their due dates. A dynamic search algorithm for the best route selection of different operations based on the job completion time is also proposed and it is implemented on a small manufacturing unit.     

Dynamic scheduling of FMS using a real-time genetic algorithm

The paper presents a genetic algorithm capable of generating optimised production plans in flexible manufacturing systems. The ability of the system to generate alternative plans following part-flow changes and unforeseen situations is particularly stressed (dynamic scheduling). Two contrasting objectives represented by the reduction of machine idle-times, thanks to dynamic scheduling computation and the reduction of the makespan, are taken into account by the proposed system. The key-point is the real-time response obtained by an optimised evolutionary strategy capable of minimising the number of genetic operations needed to reach the optimal schedule in complex manufacturing systems.     

Linguistic-based meta-heuristic optimization model for flexible job shop scheduling

In this paper, a linguistic based meta-heuristic modelling and solution approach for solving the Flexible Job Shop Scheduling Problem (FJSSP) is presented. FJSSP is an extension of the classical job-shop scheduling problem. The present problem definition is to assign each operation to a machine out of a set of capable machines ( the routing problem ) and to order the operations on the machines ( the sequencing problem ), such that a predefined performance measure is optimized. The scope of the problem is widened by taking into account the alternative process plans for each part ( process plan selection problem ) in the present study. Moreover, instead of using operations to represent product processing requirements and machine processing capabilities, machine independent capability units, which are known as Resource Elements (RE), are used. Representation of unique and shared capability boundaries of machine tools and part processing requirements is possible via RE. Using REs in scheduling can also reduce the problem size. The FJSSP is presented as a grammar and the productions in the grammar are defined as controls. Using these controls and the Giffler and Thompson (1960) priority rule-based heuristic, a simulated annealing algorithm is developed to solve FJSSP. This novel approach simplifies the modelling process of the FJSSP and enables usage of existing job shop scheduling algorithms for its solution. The results obtained from the computational study have shown that the proposed algorithm can solve this complex problem effectively within reasonable time. The results have also given some insights on the effect of the selection of dispatching rules and the flexibility level on the job shop performance. It is observed that the effect of dispatching rule selection on the job shop performance diminishes by increasing the job shop flexibility.     

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.     

Decision-making on multi-mould maintenance in production scheduling

The reliability of a critical tool like a mould on a machine affects the productivity seriously in many manufacturing firms. In fact, its breakdown frequency is even higher than machines. The decision-making on when mould maintenance should be started become a challenging issue. In the previous study, the mould maintenance plans were integrated with the traditional production schedules in a plastics production system. It was proven that considering machine and mould maintenance in production scheduling could improve the overall reliability and productivity of the production system. However, the previous model assumed that each job contained single operation. It is not workable in other manufacturing systems such as die stamping which may contain multiple operations with multiple moulds in each job. Thus, this study models a new problem for multi-mould production-maintenance scheduling. A genetic algorithm approach is applied to minimise the makespan of all jobs in 10 hypothetical problem sets. A joint scheduling (JS) approach is proposed to decide the start times of maintenance activities during scheduling. The numerical result shows that the JS approach has a good performance in the new problem and it is sensitive to the characteristic of the setup time defined.     

Scheduling with alternatives: a link between process planning and scheduling

The objective of this research is to develop and evaluate effective, computationally efficient procedures for scheduling jobs in a large-scale manufacturing system involving, for example, over 1000 jobs and over 100 machines. The main performance measure is maximum lateness; and a useful lower bound on maximum lateness is derived from a relaxed scheduling problem in which preemption of jobs is based on the latest finish time of each job at each machine. To construct a production schedule that minimizes maximum lateness, an iterative simulation-based scheduling algorithm operates as follows: (a) job queuing times observed at each machine in the previous simulation iteration are used to compute a refined estimate of the effective due date (slack) for each job at each machine; and (b) in the current simulation iteration, jobs are dispatched at each machine in order of increasing slack. Iterations of the scheduling algorithm terminate when the lower bound on maximum lateness is achieved or the iteration limit is reached. This scheduling algorithm is implemented in Virtual Factory, a Windows-based software package. The performance of Virtual Factory is demonstrated in a suite of randomly generated test problems as well as in a large furniture manufacturing facility. To further reduce maximum lateness, a second scheduling algorithm also incorporates a tabu search procedure that identifies process plans with alternative operations and routings for jobs. This enhancement yields improved schedules that minimize manufacturing costs while satisfying job due dates. An extensive experimental performance evaluation indicates that in a broad range of industrial settings, the second scheduling algorithm can rapidly identify optimal or nearly optimal schedules.     

A multi-agent protocol for multilateral negotiations in supply chain management

Within a supply chain network, it is common for companies to engage in negotiations to resolve conflicts in task allocation and order fulfilment problems. This kind of supply chain negotiation is usually regarded as buyer–seller negotiation. In recent years, multi-agent systems have been established to automate buyer–seller negotiations. However, most have limitations in handling complex negotiation scenarios such as multilateral negotiations and multi-issue negotiations. This paper presents ECNPro (the Extended Contract-Net-like multilateral Protocol), which is a new multi-agent protocol for handling buyer–seller negotiations in supply chain management. ECNPro is designed to handle agent bargaining and interactions in complex multilateral and multi-issue negotiations in which the buyer has to negotiate with many suppliers. The multi-attribute utility theory (MAUT) approach is adopted to establish the utility functions for a set of negotiation issues in the bargaining process. It adopts a multi-threaded approach to allow the buyer to bargain concurrently with multiple suppliers. ECNPro is able to split an order to more than one supplier to achieve a better negotiation payoff. In addition, mobile agents are employed in ECNPro, the buyer sends mobile agents to sites of the sellers to conduct bargaining locally. This approach improves the negotiation efficiency significantly.