Planning the routing mix in FASs to minimize total transportation time

The routing mix problem in flexible assembly systems is considered. The problem consists of assigning the operations for each part to the machines, with the two objectives of balancing the machine workloads and minimizing the burden of the transportation system. These two objectives are sometimes conflicting, since the latter tends to support assigning operations to the same machine(s) as much as possible, and this may be bad for workload balancing. A linear programming problem is presented that, given a constraint on the workload of each machine, finds one solution that minimizes the overall time spent moving the parts from one machine to another. Since such a linear program may have an exponential number of variables, an efficient column generation technique to solve the problem is devised. The efficiency of the method is validated by experiments on a large number of random problems.     

A heuristic algorithm for the loading problem in flexible manufacturing systems

The paper considers the loading problem in flexible manufacturing systems (FMSs). This problem involves the assignment to the machine tools of all operations and associated cutting tools required for part types that have been selected to be produced simultaneously. The loading problem is first formulated as a linear mixed 0–1 program with the objective to minimize the greatest workload assigned to each machine. A heuristic procedure is presented in which an assignment of operations to machine tools is obtained by solving a parameterized generalized assignment problem with an objective function that approximates the use of tool slots required by the operations assigned to the machines. The algorithm is coded in FORTRAN and tested on an IBM-compatible personal computer. Computational results are presented for different test problems to demonstrate the efficiency and effectiveness of the suggested procedure.     

Loading algorithms for flexible manufacturing systems with partially grouped unrelated machines and additional tooling constraints

This paper considers the loading problem for flexible manufacturing systems with highly flexible partial machine grouping, i.e., machines are tooled differently, but each operation can be assigned to multiple machines. Loading is the problem of allocating operations and their associated cutting tools to machines for a given set of parts. As an extension of the existing studies, we consider unrelated machines, i.e., processing time of an operation depends on the speed of the machine to which it is allocated, and dedicated machines, i.e., certain part types must be processed on a specific machine. Also, we consider the constraints associated with cutting tools: (a) tool life restrictions and (b) number of available tool copies. An integer linear programming model is suggested for the objective of balancing the workloads assigned to machines and then due to the complexity of the problem, we suggest two-stage heuristics in which an initial solution is obtained using modified bin-packing algorithms and then it is improved by a simple search technique. The two-stage heuristics suggested in this study were tested on various test instances, and the results show that they can give reasonable quality solutions within a very short amount of computation time. Also, a sensitivity analysis was done on the tightness of the tooling constraints, and the results are reported.     

Workflow balancing strategies in parallel machine scheduling

Workflow balancing on a shop floor helps to remove bottlenecks present in the manufacturing system. Workflow refers to the total time during which the work centres are busy. Idle time is not taken into account when calculating workflow. Earlier researchers have not specified the method for jobs to be executed in parallel in order to balance the workflow to each machine. In many manufacturing environments, multiple processing stations are used in parallel to obtain adequate capacity. In parallel machine scheduling there are m machines to which n jobs are to be assigned based on different priority strategies. The procedure is based on the idea of workload balancing and on balancing the workload among machines. In this paper, workflow and workload are assumed to have the same meaning. A machine with the lowest workflow is selected for assignment of a new job from the list of unfinished jobs. Different priority strategies are followed for the selection of jobs. Three different strategies are considered, namely random (RANDOM), shortest processing time (SPT) and longest processing time (LPT) for the selection of jobs for workflow balancing. The relative percentage of imbalance (RPI) is adopted among the parallel machines to evaluate the performance of these strategies in a standard manufacturing environment. The LPT rule shows better performance for the combination of larger job sizes and higher number of work centres or machines. A computer program was coded for validation in a standard manufacturing environment on an IBM/PC compatible system in the C++ language.     

Workload balance and part-transfer minimization in flexible manufacturing systems

Problems related to the flow management of a flexible manufacturing system (FMS) are here formulated in terms of combinatorial optimization. We consider a system consisting of several multitool automated machines, each one equipped with a possibly different tool set and linked to each other by a transportation system for part moving. The system operates with a given production mix.The focused flow-management problem is that of finding the part routings allowing for an optimal machine workload balancing. The problem is formulated in terms of a particular capacity assignment problem.With the proposed approach, a balanced solution can be achieved by routing parts on a limited number of different paths. Such a balancing routing can be found in polynomial time. We also give polynomial-time and-space algorithms for choosing, among all workload-balancing routings, the ones that minimize the global amount of part transfer among all machines.     

Scheduling algorithms for a two-machine flexible manufacturing system

The flexible manufacturing system (FMS) considered in this paper is composed of two CNC machines working in series—a punching machine and a bending machine connected through rollers acting as a buffer system of finite capacity. The main difference between the present problem and the standard two-machine flow shop problem with finite intermediate capacity is precisely the buffer system, which in our problem consists of two stacks of parts supported by rollers: the first stack contains the output of the punching machine, while the second stack contains the input for the bending machine. When the second stack is empty, the first stack may be moved over. Furthermore, the capacity of each stack depends on the particular part type being processed.The FMS can manufacture a wide range of parts of different types. Processing times on the two machines are usually different so that an unbalance results in their total workload. Furthermore, whenever there is a change of the part type in production, the machines must be properly reset—that is, some tools need to be changed or repositioned.A second important difference between the present problem and the usual two-machine flow shop problem is the objective. Given a list ofp part types to be produced in known quantities, the problem considered here is how to sequence or alternate the production of the required part types so as to achieve various hierarchical targets: minimize the makespan (the total time needed to complete production) and, for instance, compress the idle periods of the machine with less workload into a few long enough intervals that could be utilized for maintenance or other reasons.Although Johnson's rule is optimal in some particular cases, the problem addressed in the paper isNP-hard in general: heuristic procedures are therefore provided.     

Optimal parallel machines scheduling with machine availability and eligibility constraints

In reality, the machine might become unavailable due to machine breakdowns or various inevitable reasons, and machine might have different capability to processing job. Motivated by this, we consider the problem of scheduling n non-preemptive and independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the maximum lateness. Each machine is capable of processing at specific availability intervals. We develop a branch and bound algorithm applying several immediate selection rules for solving this scheduling problem.     

A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem

In this paper, a scheduling problem for a two-stage production system including machining operations and assembly operations is studied. In this system, a number of products of different kinds are produced. Each product is assembled with a set of several parts. The first stage is a hybrid flow shop to produce parts. All machines can process all kinds of parts in this stage, but each machine can process only one part at a time. The second stage is a single assembly machine or a single assembly team of workers. The considered objective is to minimize the completion time of all products (makespan). A mathematical modeling is presented, and since this problem has been proved strongly nondeterministic polynomial-time hard, a series of heuristic algorithms based on the basic idea of Johnson algorithm is proposed. Also, two lower bounds is introduced and improved to evaluate the final solution obtained from heuristic algorithms. The numerical experiments are used to evaluate the performance of the proposed algorithms.     

A hybrid discrete firefly algorithm for multi-objective flexible job shop scheduling problem with limited resource constraints

In this paper, a hybrid discrete firefly algorithm is presented to solve the multi-objective flexible job shop scheduling problem with limited resource constraints. The main constraint of this scheduling problem is that each operation of a job must follow a process sequence and each operation must be processed on an assigned machine. These constraints are used to balance between the resource limitation and machine flexibility. Three minimisation objectives—the maximum completion time, the workload of the critical machine and the total workload of all machines—are considered simultaneously. In this study, discrete firefly algorithm is adopted to solve the problem, in which the machine assignment and operation sequence are processed by constructing a suitable conversion of the continuous functions as attractiveness, distance and movement, into new discrete functions. Meanwhile, local search method with neighbourhood structures is hybridised to enhance the exploitation capability. Benchmark problems are used to evaluate and study the performance of the proposed algorithm. The computational result shows that the proposed algorithm produced better results than other authors’ algorithms.     

Workload balancing in printed circuit board assembly

Line balancing of a printed circuit board (PCB) assembly line is considered in the present paper. The production line consists of a number of machines for inserting electronic components on bare PCBs. The aim is to distribute the assembly operations of a single PCB type to the different machines in such a way that the throughput (i.e., the number of finished PCBs per time unit) of the line is maximized. We suppose that the total time for placements is a linear function of the number of component insertions performed by a machine. Effective mathematical formulations of the balancing problem are then available but previous models omit several aspects having an effect on the actual placement times. In particular, we extend an existing MILP formulation of the problem to consider the usage of feeder modules, precedence constraints among the placement operations, and duplication of frequently used components in several machines. We consider production lines consisting of several gantry-type placement machines. Unlike previous research, we applied standard optimization tools for solving the balancing problems. We then observed that the CPLEX-software was able to solve MILP formulations of 2- and 3-machine problems with up to 150 different component types and relatively large number of component placements (from 400 to 6,000). On the other hand, the running time was rather unstable so that heuristics are still needed for cases where exact methods fail.     

Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria

In textile industries, production facilities are established as multi-stage production flow shop facilities, where a production stage may be made up of parallel machines. This known as a flexible or hybrid flow shop environment. This paper considers the problem of scheduling n independent jobs in such an environment. In addition, we also consider the general case in which parallel machines at each stage may be unrelated. Each job is processed in ordered operations on a machine at each stage. Its release date and due date are given. The preemption of jobs is not permitted. We consider both sequence- and machine-dependent setup times. The problem is to determine a schedule that minimizes a convex combination of makespan and the number of tardy jobs. A 0–1 mixed integer program of the problem is formulated. Since this problem is NP-hard in the strong sense, we develop heuristic algorithms to solve it approximately. Firstly, several basic dispatching rules and well-known constructive heuristics for flow shop makespan scheduling problems are generalized to the problem under consideration. We sketch how, from a job sequence, a complete schedule for the flexible flow shop problem with unrelated parallel machines can be constructed. To improve the solutions, polynomial heuristic improvement methods based on shift moves of jobs are applied. Then, genetic algorithms are suggested. We discuss the components of these algorithms and test their parameters. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages.     

Cell formation in the presence of reconfigurable machines

In this research, an approach is made to design machine cells using modular machines to achieve certain characteristics of reconfigurable manufacturing. Each machine considered in the model consists of some basic and auxiliary machine modules. By changing the auxiliary modules, different operations can be performed on the machines. A similarity measure among machines based on production flow information and auxiliary module requirement is developed. Machine cells are identified using a multi-objective evolutionary genetic algorithm for a set of parts with parameters such as the volumes of production, alternative operation-based process plans, etc. The two objectives considered are the minimization of inter-cell movement and the total changes in auxiliary modules for the given production horizon. The resulting cell configuration is simulated to find the exact inter-cellular movements and the total number of module changes to validate the heuristic. An illustrative problem and experimental results are given.     

Machine cell formation for cellular manufacturing systems using an ant colony system approach

The aim of a cellular manufacturing system is to group parts that have similar processing needs into part families and machines that meet these needs into machine cells. This paper addresses the problem of grouping machines with the objective of minimizing the total cell load variation and the total intercellular moves. The parameters considered include demands for number of parts, routing sequences, processing time, machine capacities, and machine workload status. For grouping the machines, an ant colony system (ACS) approach is proposed. The computational procedure of the approach is explained with a numerical illustration. Large problems with up to 40 machines and 100 part types are tested and analyzed. The results of ACS are compared with the results obtained from a genetic algorithm (GA), and it is observed that its performance is better than that of GA.     

Scheduling of a hub reentrant job shop to minimize makespan

This paper focuses on a hub reentrant shop scheduling problem which is motivated by actual packing production line in the iron and steel industry. There are five operations for processing a job where three operations must be processed on a hub machine, and between any two consecutive operations on the hub machine, two operations must be processed on other two secondary machines, respectively. We mainly consider two types of the problem. The first is basic hub reentrant shop (BHRS) problem where only one machine in each secondary machine center. The second is hybrid hub reentrant shop (HHRS) problem where multiple machines in each secondary machine center. The objective is to minimize the makespan. For BHRS problem, we show that the problem is NP-hard in the strong sense. Some properties are derived for identifying an optimal schedule. Furthermore, a heuristic algorithm is proposed with the worst performance ratio 6:5, and this ratio is demonstrated tight. For HHRS problem, two well-solvable cases are proposed, respectively. Under a split condition, HHRS is equivalent to a two-stage hybrid flow shop problem. The worst case of a class of proposed algorithms is analyzed. The performance ratio is demonstrated relatively with the secondary machine numbers.     

Unrelated parallel machine scheduling with secondary resource constraints

This paper considers unrelated parallel machine scheduling with secondary resource constraints. There are n jobs, each needing to be processed on one of the fitted machines. A setup that includes detaching one die and attaching another from the fitted die type is incurred if the type of job scheduled is different from the last job on that machine. For each kind of die type, the number of dies available is limited. Due to the mechanical structure of the machines, the processing time of a job depends on the machine on which the job is processed, and some jobs are restricted to be processed only on certain machines. In this paper, a heuristic with a capability relative to a runtime and solution quality is developed to minimise the makespan. The performance of the presented heuristic is evaluated through extensive computational experiments. Computational results show that the presented heuristic outperforms the search method tested. It is expected that this research can be applied in industry where unrelated parallel machines are used to process different components and setups for auxiliary equipments are required.     

Parallel machine scheduling with earliness-tardiness penalties and space limits

In order to maximize an availability of machine and utilization of space, the parallel machines scheduling problem with space limit is frequently discussed in the industrial field. In this paper, we consider the parallel machine scheduling problem in which n jobs having different release times, due dates, and space limits are to be scheduled on m parallel machines. The objective function is to minimize the weighted sum of earliness and tardiness. To solve this problem, a heuristic is developed which is divided into three modules hierarchically: job selection, machine selection and job sequencing, and solution improvement. To illustrate its effectiveness, a proposed heuristic is compared with genetic algorithm (GA), hybrid genetic algorithm (HGA), and tabu search (TS), which are well-known meta-heuristics in a large number of randomly generated test problems based on the field situation. Also, we determine the job selection rule that is suitable to the problem situation considered in this paper and show the effectiveness of our heuristic method.     

Optimization of line configuration and balancing for flexible machining lines

Line configuration and balancing is to select the type of line and allot a given set of operations as well as machines to a sequence of workstations to realize high-efficiency production. Most of the current researches for machining line configuration and balancing problems are related to dedicated transfer lines with dedicated machine workstations. With growing trends towards great product variety and fluctuations in market demand, dedicated transfer lines are being replaced with flexible machining line composed of identical CNC machines. This paper deals with the line configuration and balancing problem for flexible machining lines. The objective is to assign operations to workstations and find the sequence of execution, specify the number of machines in each workstation while minimizing the line cycle time and total number of machines. This problem is subject to precedence, clustering, accessibility and capacity constraints among the features, operations, setups and workstations. The mathematical model and heuristic algorithm based on feature group strategy and polychromatic sets theory are presented to find an optimal solution. The feature group strategy and polychromatic sets theory are used to establish constraint model. A heuristic operations sequencing and assignment algorithm is given. An industrial case study is carried out, and multiple optimal solutions in different line configurations are obtained. The case studying results show that the solutions with shorter cycle time and higher line balancing rate demonstrate the feasibility and effectiveness of the proposed algorithm. This research proposes a heuristic line configuration and balancing algorithm based on feature group strategy and polychromatic sets theory which is able to provide better solutions while achieving an improvement in computing time.     

A new branch and bound algorithm for loading problems in flexible manufacturing systems

Loading problems in flexible manufacturing systems involve assigning operations for selected part types and their associated tools to machines or machine groups. One of the objectives might be to maximize the expected production rate (throughput) of the system. Because of the difficulty in dealing with this objective directly, a commonly used surrogate objective is the closeness of the actual workload allocation to the continuous workload allocation that maximizes throughput. We test several measures of closeness and discuss correlations between these measures and throughput. Using the best measure, we show how to modify an existing branch and bound algorithm which was developed for the case of equal target workloads for all machine groups to accommodate unequal target workloads. We also develop a new branch and bound algorithm which can be used for both types of problems. The efficiency of the algorithm in finding optimal solutions is achieved through the application of better branching rules and improved dominance results. Computational results on randomly generated test problems indicate that the new algorithm performs well.     

Production Capacity Modeling of Alternative, Nonidentical, Flexible Machines

Analyzing the production capacity of a flexible manufacturing system consisting of a number of alternative, nonidentical, flexible machines, where each machine is capable of producing several different part types simultaneously (by flexibly allocating its production capacity among these part types), is not a trivial task. The production capacity set of such a system is naturally expressed in terms of the machine-specific production rates of all part types. In this paper we also express it in terms of the total production rates of all part types over all machines. More specifically, we express the capacity set as the convex hull of a set of points corresponding to all possible assignments of machines to part types, where in each assignment each machine allocates all its capacity to only one part type. First, we show that within each subset of assignments having a given number of machines assigned to each part type, there is a unique assignment that corresponds to an extreme point of the capacity set. Then, we propose a procedure for generating all the extreme points and facets of the capacity set. Numerical experience shows that when the number of part types is less than four, the size of the capacity set (measured in terms of the number of variables times the number of constraints) is smaller, if the capacity set is expressed in terms of the total production rates of all part types over all machines than if it is expressed in terms of the machine-specific production rates of all part types. When the number of part types is four or more, however, the opposite is true.     

Scheduling on unrelated parallel machines with sequence- and machine-dependent setup times and due-date constraints

We consider the unrelated parallel-machine scheduling problem with sequence- and machine-dependent setup times and due-date constraints. There are N jobs, each having a due date and requiring a single operation on one of the M machines. A setup is required if there is a switch from processing one type of job to another. Due to the characteristics of machines, the processing time depends upon the job and machine on which the job is processed, and the setup time is sequence and machine dependent. In addition, certain jobs have strict due-date constraints. An effective heuristic based on a modified apparent-tardiness-cost-with-setup procedure, the simulated annealing method, and designed improvement procedures is proposed to minimize the total tardiness of this scheduling problem. Computational characteristics of the proposed heuristic are evaluated through an extensive experiment using a newly created data set. Computational results show that the proposed heuristic is able to effectively improve the initial solutions, obtained by a modified apparent-tardiness-cost-with-setup procedure, and obtains better results than a random descent heuristic.