Loading algorithms for flexible manufacturing systems with partially grouped machines

The loading problem in a Flexible Manufacturing System (FMS) involves allocating operations and associated cutting tools to machines for a given set of parts. There may be different environments for the loading problem that result from three ways of grouping machines in an PMS, i.e., no grouping, partial grouping, and total grouping. Unlike most previous studies on the loading problem for the configurations of no grouping and total grouping, this paper focuses on the loading problem resulting from partial grouping, in which each machine is tooled differently but each operation can be processed by one or more machines. Two types of heuristic algorithms are suggested for the loading problem with the objective of minimizing the maximum workload of the machines. Performances of the suggested loading algorithms are tested on randomly generated test problems and the results show that the suggested algorithms perform better than existing ones. In addition, it is found from simulation experiments that loading plans from partial grouping give significantly better performance than those from total grouping.     

JOB ASSIGNMENT ALGORITHMS ON UNIFORM PARALLEL MACHINES

Uniform parallel machine scheduling problems with a makespan measure cannot generally be solved within polynomial time complexity. This paper considers special problems with a single type of job on the uniform parallel machines, where each machine is available at a given ready time. Also the machine can be restricted on the number of jobs to be processed. The objective is to develop job assignment or batching algorithms which minimize makespan. When all the machines are available at time zero and have no restriction on the number of assignable jobs, a lower bound and optimal solution properties are derived. Based upon these properties, a polynomial algorithm is suggested to find the optimal job assignment on each machine. Three generalized problems are considered under the following situations: (1) some machines have capacity restrictions on the production batch, (2) each machine has its ready time, and (3) the jobs require series-parallel operations. The generalized problems arc also characterized and polynomial algorithms are developed for the same aim of optimal job assignment, except for the case of series-parallel operations. A heuristic algorithm is suggested with numerical tests for the series-parallel operations problem     

Feature-based design for process planning of machining processes with optimization using genetic algorithms

The development of a feature-based design environment that can be applied in the concept-to-manufacturing stages of the machining process is explained. It is broadly divided into four modules, namely, feature-based design (FBD) environment, virtual factory environment (VFE), operation-based feature mapping (OBFM) and optimization using genetic algorithms (GA). The feature-based design environment module is used for the design, modelling, synthesis, representation and validation of the components for machining application. It uses integrated features, which are predefined as feature templates in the feature library. While instancing these integrated features, they get/derive the information required for the design, modelling, process planning and manufacturing stages of the components as their attributes, from the user/knowledge base. After creating the component, integrated features present in it are validated with respect to its application, namely machining process. The VFE module defines the mathematical model of the factory in the computer, which provides the database for operations, machines, cutting tools, work pieces, etc. The knowledge base maps validated features of the component into operation sets in the first phase of the OBFM stage. Each operation in the operation sets can be carried out using different machines and cutting tools in the factory. All these possible choices are obtained in the second phase of OBFM. GA is used to find the optimal sequence of operations, machines and cutting tools for different criteria. Provisions are also available to generate NC codes for operations, which are to be carried out with NC or CNC machines, if selected. Thus, the optimal process plan for the selected criteria with respect to the given factory environment is found for the modelled component. The feature-based design system developed is built on existing CAD, programming and spread-sheet software tools, namely CATIA®, MS-Visual Basic® and MS-Excel®, which not only save developmental effort, but also make full use of the functionalities of these commercial softwares. This paper explains the developed system with a case study.     

Loading and scheduling for flexible manufacturing systems with controllable processing times

This study addresses the problem of determining the allocation of operations and their tools to machines, the operation processing times and the allocation/sequence of the parts to be processed on each machine for flexible manufacturing systems with controllable processing times. Tool lives, tool copies and tool sharing are also considered. An integer programming model is developed for the objective of minimizing the sum of operation processing and tardiness costs. Then, iterative algorithms are proposed that solve the two subproblems iteratively, where the loading subproblem is solved by a modified bin packing algorithm under initial processing times and the resulting scheduling subproblem is solved by a priority scheduling method while modifying the loading plans and operation processing times iteratively. Computational experiments were carried out, and the results are reported.     

A part-and-tool assignment method for the workload-balance between machines and the minimisation of tool-shortage occurrences in an FMS

In this paper, we look into the loading problem of a flexible manufacturing system (FMS) that is made up of several identical flexible manufacturing machines (CMMs). These machines are capable of different operations as long as the required tools are provided to them. The loading problem studied in this paper is a pre-release problem that deals with the pre-assignment of parts and tools before the process of an FMS begins. There are two objectives that one would like to achieve. They include minimising the number of tool-shortage occurrences and balancing the workload between machines. Since one cannot directly minimise the number of tool-shortage occurrences at the current pre-release stage, a surrogate objective of minimising the total tool-capacity shortage (TTCS) is adopted. Furthermore, because of the ‘tool movement policy’ assumption, our loading problem only involves assigning parts and tools to each machine. In this paper, we propose a part-and-tool assignment method that combines fuzzy c-means, SA (simulated annealing), and an optimal tool-assignment algorithm. The proposed part-and-tool assignment method is designed to be interactive. Because of this interactive nature, human designers can experiment with different evaluation criteria or reset the parameters of SA to look for alternative solutions. An example is given which illustrates the proposed part-and-tool assignment method. From the example, one can see that the proposed method is very efficient and effective in finding good-quality solutions.     

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.     

Impact of throughput-based objectives and machine grouping decisions on the short-term performance of flexible manufacturing systems

The most commonly-used objective in the literature for solving machine loading and grouping problems in flexible manufacturing systems is the maximization of steady-state throughput. In reality, orders arrive dynamically and the mix of products changes frequently, raising questions about the applicability of this objective in achieving shorter-term measures of the output rate. Moreover, the loading and grouping problems only determine which operations are to be performed on each machine, and whether any of the machines should be identically tooled so as to allow multiple routeings for some jobs. The actual short-term performance of the system also depends on scheduling and dispatching decisions. We study the impact of the various objectives ostensibly related to steady-state throughput and machine grouping decisions on the short-term makespan performance (in a static setting). Computational results suggest that minimizing the maximum percentage overload (relative to the optimal continuous workload allocation) across machine groups is an excellent objective. The results also indicate that reducing the number of machine groups and balancing workloads among the machines help to reduce makespan.     

A GA-based solution approach for balancing printed circuit board assembly lines

Printed circuit board (PCB) assembly lines consist of a number of different machines for mounting electronic components onto PCBs. While high-speed placement machines are employed to assemble standard components, so-called fine-pitch placement machines are used to mount complex electronic components with high precision and by use of specific nozzles. In this paper, we investigate a typical mass production environment where a single type of PCB is assembled in a line comprising high-speed as well as high-precision placement machines. The PCB assembly line balancing problem consists of assigning component feeders, each holding a specific electronic component type, and the corresponding placement operations to machines in the line so as to minimize the assembly cycle time. To solve this problem, a two-stage solution procedure based on genetic algorithm (GA) is proposed. In the first stage, component feeders are assigned to the placement machines with the objective of balancing the workload within the assembly line. A number of candidate solutions are then transmitted to the second stage, where specific machine optimization algorithms are applied to determine the feeder-slot assignment in the component magazine of the machines and the placement sequence of the various components. As a result, fine-tuned placement operation times are achieved which reflect the individual operation mode and the actual component setup of the placement machines. Finally, from the candidate solutions the one which minimizes the actual PCB assembly time is selected.     

AN OPERATION-SEQUENCE-BASED APPROACH IN DESIGNING A FLOW LINE INDEPENDENT-CELL SYSTEM WITH MACHINE CAPACITY INCORPORATED

This paper considers a problem of designing a flow line independent-cell system where each machine can treat multiple production operations and at most two machines of each machine type can be installed in the same cell. The objective is to minimize the total system cost including machine cost and material handling cost subject to each cell capacity. The problem is characterized as NP-hard. Therefore, in order to find a good solution efficiently, this paper proposes two greedy-type heuristic algorithms including a single-combining algorithm and a double-combining algorithm. Both the algorithms are derived by using the process of combining the cells and are tested for their efficiencies with various numerical problems.     

Approach to measure the mix response flexibility of manufacturing systems

The mix response flexibility of a manufacturing system is the ability to change between product types quickly and economically. This paper proposes a new approach to measure this flexibility in terms of both capability and capacity. While the processing capability is represented as the number of operations that the machines can perform, the manufacturing capacity is modelled as the efficiency of different machines. The proposed model is applied to measure the mix response flexibility for both single and multiple machine systems.     

Mixed integer programming for scheduling surface mount technology lines

This paper presents new mixed integer programming formulations for blocking scheduling of SMT (Surface Mount Technology) lines for printed wiring board assembly. The SMT line consists of several processing stages in series, separated by finite intermediate buffers, where each stage has one or more identical parallel machines. A board that has completed processing on a machine may remain there and block the machine until a downstream machine becomes available for processing. The objective is to determine an assembly schedule for a mix of board types so as to complete the boards in a minimum time. Scheduling with continuous or with limited machine availability is considered. Numerical examples and some computational results are presented to illustrate applications of the models proposed.     

PCB assembly scheduling for collect-and-place machines using genetic algorithms

In printed circuit board (PCB) assembly, collect-and-place machines, which use a revolver-type placement head to mount electronic components onto the board, represent one of the most popular types of assembly machinery. The assignment of feeders to slots in the component magazine and the sequencing of the placement operations are the main optimisation problems for scheduling the operations of an automated placement machine. In this paper, we present different genetic algorithms (GAs) for simultaneously solving these highly interrelated problems for collect-and-place machines in PCB assembly. First we consider single-gantry machines as the basic type of machinery. In the conventional GA approach all placement operations and the feeder-slot assignment are represented by a single chromosome. In order to increase the efficiency of the genetic operators, we present a novel GA approach, which integrates a clustering algorithm for generating sub-sections of the PCB and grouping the corresponding placement operations. It is shown that the proposed GAs can be extended to schedule dual-gantry placement machines, which are equipped with two independent placement heads and two dedicated component magazines. Hence, component feeders have to be allocated between the two magazines. To solve this allocation problem, two different heuristic strategies are proposed. Finally, detailed numerical experiments are carried out to evaluate the performances of the proposed GAs.     

A branch-and-bound algorithm for the cell formation problem

The Cell Formation Problem (CFP) is an important optimisation problem in manufacturing. It has been introduced in the Group Technology (GT) and its goal is to group machines and parts processed on them into production cells minimising the movement of parts to other cells for processing and maximising for each cell the loading of its machines with operations on its parts. We consider one of the computationally hardest formulations of this problem – the CFP with a variable number of cells and the grouping efficacy objective, which is a fractional function. The CFP literature contains many heuristic algorithms, but only a small number of exact approaches especially for this formulation. In the current paper, we present an exact branch-and-bound algorithm for the same hard CFP formulation. To linearise the fractional objective function, we apply the Dinkelbach approach. We have been able to solve 24 of the 35 instances from the well known GT benchmark. For the remaining 11 instances, the difference in the grouping efficacy with the best known solutions is less than 2.6%.     

An integrated scheduling and material-handling approach for complex job shops: a computational study

We suggest an extension of the shifting bottleneck heuristic for complex job shops that takes the operations of automated material-handling systems (AMHS) into account. The heuristic is used within a rolling horizon approach. The job-shop environment contains parallel batching machines, machines with sequence-dependent setup times, and re-entrant process flows. Jobs are transported by an AMHS. Semiconductor wafer fabrication facilities (wafer fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic (SBH) uses a disjunctive graph to decompose the overall scheduling problem into scheduling problems for single machine groups and for transport operations. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). We consider SSPs based on dispatching rules. In this paper, we are also interested in how much we can gain in terms of TWT if we apply more sophisticated SSPs for scheduling the transport operations. We suggest a Variable Neighbourhood Search (VNS) based SSP for this situation. We conduct simulation experiments in a dynamic job-shop environment in order to assess the performance of the suggested algorithms. The integrated SBH outperforms common dispatching rules in many situations. Using near to optimal SSPs leads to improved results compared with dispatching based SSPs for the transport operations.     

Solving cell formation and task scheduling in cellular manufacturing system by discrete bacteria foraging algorithm

We consider a joint decision model of cell formation and task scheduling in cellular manufacturing system under dual-resource constrained (DRC) setting. On one hand, machines and workers are multi-functional and/or multi-skilled, and they are grouped into workstations and cells. On the other hand, there is a processing sequence among operations of the parts which needs to be dispatched to the desirable workstations for processing. Inter-cell movements of parts can reduce the processing times and the makespan but will increase the inter-cell material handling costs. The objective of the problem is to minimise the material handling costs as well as the fixed and operating costs of machines and workers. Due to the NP-hardness of the problem, we propose an efficient discrete bacteria foraging algorithm (DBFA) with elaborately designed solution representation and bacteria evolution operators to solve the proposed problem. We tested our algorithm using randomly generated instances with different sizes and settings by comparing with the original bacteria foraging algorithm and a genetic algorithm. Our results show that the proposed DBFA has better performance than the two compared algorithms with the same running time.     

A reactive GRASP and Path Relinking for balancing reconfigurable transfer lines

A line balancing problem for reconfigurable transfer lines with sequence-dependent setup times and parallel machines was studied. These lines are paced and serial, i.e. a part to be machined passes through a sequence of stations. Stations are composed of CNC (Computer Numerical Control) machines. At least one CNC machine is installed at each station. These CNC machines are mono-spindle head machines, hence setup times between operations have to be taken into account. The origins of setup times are various, for example, the necessity to rotate the part, change and displace the tool, etc. Because of setup times, the station workload depends on the sequence in which the operations are assigned to the station. In addition, accessibility constraints have to be considered. The objective consists of assigning a given set of operations as well as machines to a sequence of workstations in order to minimise the total cost of the line. Keeping in mind the industrial importance of this problem and the lack of available methods in the literature tackling it efficiently, we propose a new heuristic based on GRASP combined with Path Relinking. A MIP approach is used to select the sequences of operations on workstations. Numerical experiments are presented and show that the proposed heuristic can provide good solutions even for large-sized instances while requiring a computational time that is fully compatible with a practical application. An industrial case study is also described.     

Scheduling on Parallel Machines to Minimize Two Criteria Related to Job Tardiness

This paper deals with the scheduling of independent, nonpreemptible jobs with due dates on parallel machines. The machines are allowed to have different rates of operation, though a special algorithm is developed for the case in which they are all identical. The principal objective treated is minimizing the number of processors required to meet all due date constraints; in addition, it is shown that the solution methods for this first problem may be used to minimize maximum tardiness on a fixed number of machines. A lower bound on the number of machines required is developed, and several approximation algorithms are presented. Two enumerative optimization algorithms are developed. Computational results are presented for the case of identical machines.     

A review of discrete-time optimization models for tactical production planning

This study presents a review of optimization models for tactical production planning. The objective of this research is to identify streams and future research directions in this field based on the different classification criteria proposed. The major findings indicate that: (1) the most popular production-planning area is master production scheduling with a big-bucket time-type period; (2) most of the considered limited resources correspond to productive resources and, to a lesser extent, to inventory capacities; (3) the consideration of backlogs, set-up times, parallel machines, overtime capacities and network-type multisite configuration stand out in terms of extensions; (4) the most widely used modelling approach is linear/integer/mixed integer linear programming solved with exact algorithms, such as branch-and-bound, in commercial MIP solvers; (5) CPLEX, C and its variants and Lindo/Lingo are the most popular development tools among solvers, programming languages and modelling languages, respectively; (6) most works perform numerical experiments with random created instances, while a small number of works were validated by real-world data from industrial firms, of which the most popular are sawmills, wood and furniture, automobile and semiconductors and electronic devices.     

Capacity allocation problem in flexible manufacturing systems: branch and bound based approaches

This study considers an operation assignment and capacity allocation problem that arises in flexible manufacturing systems. The machines have limited time and tool magazine capacities and the available tools are limited. Our objective is to maximise total weight of assigned operations. We develop a branch and bound algorithm that finds the optimal solutions and a beam search algorithm that finds high quality solutions in polynomial time.     

Minimizing the makespan for the two-machine scheduling problem with a single server: Two algorithms for very large instances

This article considers the problem of scheduling a given set of n jobs on two identical parallel machines with a single server. Each job must be processed on one of the machines. Before processing, the server has to set up the relevant machine. The objective is to minimize the makespan. For this unary NP-hard problem, two fast constructive algorithms with a complexity of O(n²) are presented. The performance of these algorithms is evaluated for instances with up to 10,000 jobs. Computational results indicate that the algorithms have an excellent performance for very large instances so that the obtained objective function values are very close to a lower bound, and in many cases even an optimal solution is achieved. Superiority over all existing algorithms is obtained by sequencing the jobs on the two machines so that the machine idle time and the server waiting time are minimized. In doing so, the characteristics of an optimal solution resulting from its relevant lower bound are taken into account.