Scenario-based heuristic to two-stage stochastic program for the parallel machine ScheLoc problem

Scheduling-Location (ScheLoc) problem is a new and interesting topic in manufacturing, considering location and scheduling decisions simultaneously. Most existing works focus on the deterministic problems. In practice, however, job-processing times are usually uncertain due to some factors. This paper investigates the stochastic parallel machine ScheLoc problem to minimise the weighted sum of the location cost and the expectation of the total completion time. A two-stage stochastic programming formulation is proposed, then the sample average approximation (SAA) method is adapted to solve the small-size problems. To efficiently address the large-scale problems, a genetic algorithm (GA) and a scenario-based heuristic are designed. Numerical experiments on 450 instances are conducted. Computational results show that the scenario-based heuristic outperforms SAA method and GA in terms of solution quality and computational time.     

A flower pollination algorithm for the double-floor corridor allocation problem†

This research explores the double-floor corridor allocation problem (DFCAP), which deals with the optimal arrangement of departments over two floors and then place them along both sides against a corridor. This problem is a natural extension of the corridor allocation problem (CAP) to additional floors; the layout of each floor can be regarded as an approximately independent CAP. The DFCAP is commonly observed in manufacturing and service buildings. In this study, a mixed-integer programming formulation for the DFCAP is developed, and it is able to reduce to the classical CAP model. Then a novel flower pollination algorithm is provided, which is discretised using swap pair set approach to solve the considered DFCAP. In addition, to ameliorate the algorithm, three constructive heuristic rules are developed to produce a reasonably good initial population; meanwhile, a variable neighbourhood search structure is presented to prevent prematurity in arrival at a poor local solution. Finally, several instances for the DFCAP with a size of 9?≤?n?≤?80 are employed in the algorithms, as well as in mixed-integer non-linear programming (MINLP) formulations, which are solved with GUROBI 7.0.1. Moreover, the above-mentioned instances are utilized to show that the proposed algorithm performs better in comparison to the state-of-the-art optimization algorithms.     

Stochastic two-sided U-type assembly line balancing: a genetic algorithm approach

In this paper, a novel stochastic two-sided U-type assembly line balancing (STUALB) procedure, an algorithm based on the genetic algorithm and a heuristic priority rule-based procedure to solve STUALB problem are proposed. With this new proposed assembly line design, all advantages of both two-sided assembly lines and U-type assembly lines are combined. Due to the variability of the real-life conditions, stochastic task times are also considered in the study. The proposed approach aims to minimise the number of positions (i.e. the U-type assembly line length) as the primary objective and to minimise the number of stations (i.e. the number of operators) as a secondary objective for a given cycle time. An example problem is solved to illustrate the proposed approach. In order to evaluate the efficiency of the proposed algorithm, test problems taken from the literature are used. The experimental results show that the proposed approach performs well.     

Optimal versus heuristic scheduling of surface mount technology lines

This paper presents and compares an exact and a heuristic approach for scheduling of printed wiring board assembly in surface mount technology (SMT) lines. A typical SMT line consists of several assembly stations in series and/or in parallel, separated by finite intermediate buffers. The objective of the scheduling problem is to determine the detailed sequencing and timing of all assembly tasks for each individual board, so as to maximize the line's productivity, which is defined in terms of makespan for a mix of board types. The limited intermediate buffers between stations result in a scheduling problem with machine blocking, where a completed board may remain on a machine and block it until a downstream machine becomes available. In addition, limited machine availability due to scheduled downtimes is considered. The exact approach is based on a mixed integer programming formulation that can be used for optimization of assembly schedules by using commercially available software for integer programming, whereas the heuristic approach is designed as a combination of tabu search and a set of dispatching rules. Numerical examples modelled after real-world SMT lines and some computational results are provided to illustrate and compare the two approaches.     

A scheduling problem in glass manufacturing

In this paper, a production scheduling problem in glass manufacturing is studied. The production facility consists of multiple identical production lines and each production line includes a number of serially arranged machines. The production is characterized by semi-ordered processing times in each product family, and the last machine in each production line is a bottleneck machine. Significant changeover times are required when products of different families are produced on a production line. The scheduling problem was modeled as a parallel no-delay flowshop scheduling problem (PNDFSP). The PNDFSP combines the parallel machine scheduling problem (PMSP) with the no-delay flowshop scheduling problem (NDFSP). While PMSP and NDFSP have received considerable attention in the literature, PNDFSP has not been well studied. A mixed-integer programming formulation is developed and an efficient heuristic algorithm is proposed. The sequential heuristic algorithm considers simultaneously the line changeover time, no-delay effect, and line utilization in assigning product families to the production lines. The computational results are reported.     

Balancing Multi-Manned Assembly Lines With Walking Workers: Problem Definition,Mathematical Formulation,and an Electromagnetic Field Optimisation Algorithm

Assembly lines are widely used in industrial environments that produce standardised products in high volumes. Multi-manned assembly line is a special version of them that allows simultaneous operation of more than one worker at the same workstation. These lines are widely used in large-sized product manufacturing since they have many advantages over the simple one. This article has dealt with multi-manned assembly line balancing problem with walking workers for minimising the number of workers and workstations as the first and second objectives, respectively. A linear mixed-integer programming formulation of the problem has been firstly addressed after the problem definition is given. Besides that, a metaheuristic based on electromagnetic field optimisation algorithm has been improved. In addition to the classical electromagnetic field optimisation algorithm, a regeneration strategy has been applied to enhance diversification. A particle swarm optimisation algorithm from assembly line balancing literature has been modified to compare with the proposed algorithm. A group of test instances from many precedence diagrams were generated for evaluating the performances of all solution methods. Deviations from lower bound values of the number of workers/workstations and the number of optimal solutions obtained by these methods are concerned as performance criteria. The results obtained by the proposed programming formulations have been also compared with the solutions obtained by the traditional mathematical model of the multi-manned assembly line. Through the experimental results, the performance of the metaheuristic has been found very satisfactory according to the number of obtained optimal solutions and deviations from lower bound values.     

Minimizing makespan in a two-stage flow shop with parallel batch-processing machines and re-entrant jobs

Against a background of heat-treatment operations in mould manufacturing, a two-stage flow-shop scheduling problem is described for minimizing makespan with parallel batch-processing machines and re-entrant jobs. The weights and release dates of jobs are non-identical, but job processing times are equal. A mixed-integer linear programming model is developed and tested with small-scale scenarios. Given that the problem is NP hard, three heuristic construction methods with polynomial complexity are proposed. The worst case of the new constructive heuristic is analysed in detail. A method for computing lower bounds is proposed to test heuristic performance. Heuristic efficiency is tested with sets of scenarios. Compared with the two improved heuristics, the performance of the new constructive heuristic is superior.     

Efficient Solutions to a Linear Programming Model for Production Scheduling With Capacity Constraints and No Initial Stock

In this paper we present a decomposition approach to solve large scale linear programming models for production scheduling when there are multiple capacity-constrained facilities. The formulation assumes that there are no initial inventories, and hence is most useful in a planning environment where the current shop status is not the primary concern. The approach can be implemented as an exact procedure or with heuristic stopping rules. We determine problem characteristics for which the decomposition approach is faster than LP, so that very large problems could be solved. Problem difficulty is found to be related to size and tightness of the capacity constraints. Quality-of-solution versus CPU time tradeoffs are given for various stopping rules. Finally, we discuss the potential importance of this formulation and approach in manufacturing problems.     

A heuristic based on Vogel's approximation method for sequencing mixed-model assembly lines

Sequencing mixed-model assembly lines is a well researched topic in the literature. However, many methods that have been developed to solve this problem fail to cope with either the large size or the specific characteristics of real-life problems. In this paper, a heuristic is proposed that is derived from Vogel's approximation method for transportation planning. The heuristic is able to handle large and supposedly difficult problem instances. Sophisticated test scenarios considering real-life aspects were generated to evaluate the performance of the heuristic for realistic problem instances. It is shown that the proposed heuristic significantly outperforms priority rule-based methods and requires only reasonable computational effort.     

Scheduling manufacturing systems for delayed product differentiation in agile manufacturing

Production of customized products to respond to changing markets in a short time and at a low cost for agile manufacturing can be implemented with delayed product differentiation in a manufacturing system. The successful implementation of delayed product differentiation lies in efficient scheduling of the manufacturing system. Scheduling problems in implementing delayed product differentiation in a general flexible manufacturing system are defined, formulated and solved here. The manufacturing system consists of two stages: machining and assembly. At the machining stage, a single machine is used to produce standard component parts for assembly products. These parts are then assembled at the assembly stage by multiple identical assembly stations to form customized products. The products to be produced in the system are characterized by their assembly sequences represented by digraphs. The scheduling problem is to determine the sequence of products to be produced in the system so that the maximum completion time (makespan) is minimized for any given number of assembly stations at the assembly stage. Based on the representation of assembly sequence of the products, three production modes are defined: production of a single product with a simple assembly sequence ; production of a single product with a complex assembly sequence ; and production of N products . According to the three defined production modes, the associated scheduling problems are defined as G s scheduling problems, G c scheduling problems and N-product scheduling problems, respectively. Optimal and heuristic methods for solving the scheduling problems are developed. The computational experiment shows that the heuristics provide good solutions to the scheduling problems.     

Sequencing mixed-model assembly lines operating with a heterogeneous workforce

We study the problem of sequencing mixed-model assembly lines operating with a heterogeneous workforce. The practical motivation for this study comes from the context of managing assembly lines in sheltered work centres for the disabled. We propose a general framework in which task execution times are both worker and model dependent. Within this framework, the problem is defined and mathematical mixed-integer models and heuristic procedures are proposed. These include a set of fast constructive heuristics, two local search procedures based on approximate measures using either a solution upper bound or the solution of a linear program and a GRASP metaheuristic. Computational tests with instances adapted from commonly used literature databases are used to validate the proposed approaches. These tests give insight on the quality of the different techniques, which prove to be very efficient both in terms of computational effort and solution quality when compared to other strategies such as a random sampling or the solution of the MIP models using a commercial solver.     

Scheduling algorithms for remanufacturing systems with parallel flow-shop-type reprocessing lines

This study considers a scheduling problem for remanufacturing systems in which end-of-life products are separated into their major components at a disassembly workstation, each of them is reprocessed at its dedicated flow-shop-type reprocessing line with serial workstations, and finally, the reprocessed components, together with new components if required, are reassembled into remanufactured products at a reassembly workstation. Among various system configurations, we focus on the one with parallel flow-shop-type reprocessing lines since it is a typical remanufacturing configuration. The problem is to determine the sequence of products to be disassembled, the sequence of components to be reprocessed at each workstation of flow-shop-type reprocessing lines and the sequence of products to be reassembled for the objective of minimising the total flow time. An integer programming model is developed to represent the problem mathematically, and then, three types of heuristics, i.e. priority rule-based heuristic, Nawaz–Enscore–Ham-based heuristic and iterated greedy algorithm, are proposed due to the problem complexity. To show the performances of the heuristics, a series of computational experiments were done on various test instances, and the results are reported.     

Balancing two-sided assembly lines with sequence-dependent setup times

Two-sided assembly lines are often designed to produce large-sized products, such as automobiles, trucks and buses. In this type of production line, both left-side and right-side of the line are used in parallel. In all studies on two-sided assembly lines, sequence-dependent setup times have not yet been considered. However, in real life applications, setups may exist between tasks. Performing a task directly before another task may influence the latter task inside the same station, because a setup for performing the latter task may be required. Furthermore, if a task is assigned to a station as the last one, then it may cause a setup for performing the first task assigned to that station since the tasks are performed cyclically. In this paper, the problem of balancing two-sided assembly lines with setups (TALBPS) is considered. A mixed integer program (MIP) is proposed to model and solve the problem. The proposed MIP minimises the number of mated-stations (i.e., the line length) as the primary objective and it minimises the number of stations (i.e., the number of operators) as a secondary objective for a given cycle time. A heuristic approach (2-COMSOAL/S) for especially solving large-size problems based on COMSOAL (computer method of sequencing operations for assembly lines) method is also presented. An illustrative example problem is solved using 2-COMSOAL/S. To assess the effectiveness of MIP and 2-COMSOAL/S, a set of test problems are solved. The computational results show that 2-COMSOAL/S is very effective for the problem.     

A similarity score-based two-phase heuristic approach to solve the dynamic cellular facility layout for manufacturing systems

The dynamic cellular facility layout problem (DCFLP) is a well-known NP-hard problem. It has been estimated that the efficient design of DCFLP reduces the manufacturing cost of products by maintaining the minimum material flow among all machines in all cells, as the material flow contributes around 10–30% of the total product cost. However, being NP hard, solving the DCFLP optimally is very difficult in reasonable time. Therefore, this article proposes a novel similarity score-based two-phase heuristic approach to solve the DCFLP optimally considering multiple products in multiple times to be manufactured in the manufacturing layout. In the first phase of the proposed heuristic, a machine–cell cluster is created based on similarity scores between machines. This is provided as an input to the second phase to minimize inter/intracell material handling costs and rearrangement costs over the entire planning period. The solution methodology of the proposed approach is demonstrated. To show the efficiency of the two-phase heuristic approach, 21 instances are generated and solved using the optimization software package LINGO. The results show that the proposed approach can optimally solve the DCFLP in reasonable time.     

Tabu search-based algorithm for the TOC product mix decision

The theory of constraints (TOC) is a management philosophy that maximizes profits in a manufacturing plant with a demonstrated bottleneck. The product mix decision is one application of TOC that involves determination of the quantity and the identification of each product to produce. However, the original TOC heuristic is considered to produce unrealizable solution when a manufacturing plant has multiple resource constraints. This paper presents a tabu search-based TOC product mix heuristic to identify optimal or near optimal product mix for small problem instances under conditions where the original TOC heuristic failed. The tabu search-based TOC product mix heuristic is further used to solve large problem instances typical of practical manufacturing scenario. The experimental results for small to medium size problem show that the tabu search-based TOC heuristic compares favourably with those of optimal methods. Large size problems for which optimal methods have not been established in terms of feasibility in computation times were also solved in reasonable times with good quality solutions, thus confirming that the proposed approach is appropriate for adoption by production planners for the product mix problem in the manufacturing industry.     

Balancing of mixed-model parallel U-shaped assembly lines considering model sequences

As a consequence of increasing interests in customised products, mixed-model lines have become the most significant components of today’s manufacturing systems to meet surging consumer demand. Also, U-shaped assembly lines have been shown as the intelligent way of producing homogeneous products in large quantities by reducing the workforce need thanks to the crossover workstations. As an innovative idea, we address the mixed-model parallel U-shaped assembly line design which combines the flexibility of mixed-model lines with the efficiency of U-shaped lines and parallel lines. The multi-line stations utilised in between two adjacent lines provide extra efficiency with the opportunity of assigning tasks into workstations in different combinations. The new line configuration is defined and characterised in details and its advantages are explained. A heuristic solution approach is proposed for solving the problem. The proposed approach considers the model sequences on the lines and seeks efficient balancing solutions for their different combinations. An explanatory example is also provided to show the sophisticated structure of the studied problem and explain the running mechanism of the proposed approach. The results of the experimental tests and their statistical analysis indicated that the proposed line design requires fewer number of workstations in comparison with independently balanced mixed-model U-lines.     

Mathematical formulation and heuristic algorithms for optimisation of auto-part milk-run logistics network considering forward and reverse flow of pallets

The operational planning of distribution network for automotive industry is complex with many conditions to consider, including heterogeneous fleet, enforcing the feasibility of 3D-packing of pallets into vehicles to address the vehicle's capacity in terms of weight and volume, compatibility of orders in a vehicle, returning empty pallets from assembly-plants backwards to suppliers, and delivery time windows. A mathematical model (MILP) is proposed that takes account of these conditions to minimise total transportation costs. The network structure can be a combination of direct shipment and milk-run for both forward and reverse flow of pallets. The model is solved optimally for small-size problems. For solving larger problems, a heuristic algorithm (in two versions) is proposed that uses a similarity measure to generate a reasonable list of orders. Best/first-fit strategies are employed to generate a feasible solution with the aid of a relaxed version of the proposed MILP. Improvement heuristics are also designed. Unlike most of existing constructive heuristics, our aim for developing the heuristic approach is to force routing decision, with all of its considerations, being made optimal. We also use the proposed best-fit strategy in the body of grouping evolution strategy (GES) algorithm to attain an effective meta-heuristic approach. The effectiveness of heuristics is tested on generated instances which demonstrates they are optimal for small-size problems. They are also tested on the data of daily auto-parts shipments gathered from the largest Iranian automobile company. Results demonstrate there exists a significant potential for cost saving through milk-run strategy compared with the direct shipping strategy.     

Mixed-integer linear programming method for multi-degree and multi-hoist cyclic scheduling with time windows

Multi-degree cyclic hoist scheduling and multi-hoist cyclic scheduling are both capable of improving the throughput in an automatic electroplating line. However, previous research on integrated multi-degree and multi-hoist cyclic scheduling is rather limited. This article develops an optimal mixed-integer linear programming model for the integrated multi-degree and multi-hoist cyclic scheduling with time window constraints. This model permits overlap on hoist coverage ranges, and it proposes new formulations to avoid hoist collisions, by which time window constraints and tank capacity constraints are also formulated. A set of available benchmark instances and newly generated instances are solved using the CPLEX solver to test the performance of the proposed method. Computational results demonstrate that the proposed method outperforms the zone partition heuristic without overlapping, and the throughputs are improved by a significant margin using the proposed method, especially for large-size instances.     

Optimal selection of module instances for modular products in reconfigurable manufacturing systems

A method for optimizing the variety of a modular products, manufactured in a Reconfigurable Manufacturing System, is proposed. The optimization is achieved through appropriately selecting the subsets of module instances from given sets. The problem is formulated as an integer nonlinear programming problem to find a trade-off between the quality loss due to modularity and the cost of reconfiguration for given sets of customer requirements. The proposed formulation is general in the sense that products can have any number of modules. The formulation is an extension to the available formulation that was developed for products with only two modules. Moreover, the current work addresses the effect of different order priorities, customer importance, and demands. The proposed method has been applied to a modular assembly problem and found to be efficient in determining optimum subsets of module instances.     

An ant colony optimisation algorithm for scheduling in agile manufacturing

Producing customised products in a short time at low cost is one of the goals of agile manufacturing. To achieve this goal an assembly-driven differentiation strategy has been proposed in the agile manufacturing literature. In this paper, we address a manufacturing system that applies the assembly-driven differentiation strategy. The system consists of machining and assembly stages, where there is a single machine at the machining stage and multiple identical assembly stations at the assembly stage. An ant colony optimisation (ACO) algorithm is developed for solving the scheduling problem of determining the sequence of parts to be produced in the system so as to minimise the maximum completion time (or makespan). The ACO algorithm uses a new dispatching rule as the heuristic desirability and variable neighbourhood search as the local search to make it more efficient and effective. To evaluate the performance of heuristic algorithms, a branch-and-bound procedure is proposed for deriving the optimal solution to the problem. Computational results show that the proposed ACO algorithm is superior to the existing algorithm, not only improving the performance but also decreasing the computation time.