A special case of transfer lines balancing by graph approach

A balancing problem for paced production lines with workstations in series and blocks of parallel operations at the workstations is considered. Operations of each workstation are partitioned into blocks. All operations of the same block are performed simultaneously by one spindle head. All blocks of the same workstation are also executed simultaneously. The relations of the necessity of executing some operations at the same workstation, the possibility of combining the blocks at the same workstation as well as precedence constraints are given. The operation time of the workstation is the maximal value among operation times of its blocks. The line cycle time is the maximal workstation time. The problem is to choose blocks from a given set and allocate them to workstations in such a way that (i) all the operations are assigned, (ii) the above constraints are satisfied, (iii) a given cycle time is not exceeded, and (iv) the line cost is minimal. A method for solving the problem is based on its transformation to a constrained shortest path problem.     

Branch and bound algorithm for a transfer line design problem: Stations with sequentially activated multi-spindle heads

In this paper, a new transfer line balancing problem is considered. The main difference from the simple assembly line balancing problem is that the operations are grouped into blocks (batches). All the operations of the same block are carried out simultaneously by one piece of equipment (multi-spindle head). Nevertheless, the blocks assigned to the same workstation are executed in series. The line cost consists of the sum of block and workstation costs. At the considered line design stage, the set of all available blocks is given. The aim is to find a subset from the given set of available blocks and to find a partition of this subset to workstations such that each operation is executed once and the line cost is minimal while all the precedence, cycle time, and compatibility (operation inclusion and block exclusion) constraints are respected. A new lower bound based on solving a special set partitioning problem is presented and a branch and bound algorithm is developed. The experimental results prove the quality of the lower bound and applicability of the suggested branch and bound algorithm for medium sized industrial cases.     

Modelling transfer line design problem via a set partitioning problem

The design of a transfer line is considered. This line is used for a repetitive execution of a given set of operations to produce identical items. The line is composed of a sequence of workstations equipped with processing modules (blocks). Each block performs specific operations. The machined items move along the workstations in the same direction. There is the same cost associated with each workstation and different costs associated with diverse blocks. The problem is to determine the number of workstations, select a set of blocks and assign the selected blocks to the workstations so that, for each item, each operation is performed exactly once with total line cost to be minimized. The specificity of the problem is that all operations of the same workstation are performed in parallel. There are inclusion, exclusion, and precedence relations that restrict the assignment of blocks and operations to the same workstation and constrain the processing order of the operations on the transfer line. We suggest a reduction of this transfer line design problem to a simple set partitioning problem. This reduction is based on the concept of a locally feasible workstation.     

A heuristic multi-start decomposition approach for optimal design of serial machining lines

We study an optimal design problem for serial machining lines. Such lines consist of a sequence of stations. At every station, the operations to manufacture a product are grouped into blocks. The operations within each block are performed simultaneously by the same spindle head and the blocks of the same station are executed sequentially. The inclusion and exclusion constraints for combining operations into blocks and stations as well as the precedence constraints on the set of operations are given. The problem is to group the operations into blocks and stations minimizing the total line cost. A feasible solution must respect the given cycle time and all given constraints. In this paper, a heuristic multi-start decomposition approach is proposed. It utilizes a decomposition of the initial problem into several sub-problems on the basis of a heuristic solution. Then each obtained sub-problem is solved by an exact algorithm. This procedure is repeated many times, each time it starts with a new heuristic solution. Computational tests show that the proposed approach outperforms simple heuristic algorithms for large-scale problems.     

Balancing modular transfer lines with serial-parallel activation of spindle heads at stations

The paper deals with an as yet unexplored combinatorial optimization problem concerning balancing complex transfer lines in the machining/process environment. In contrast to similar problems for assembly lines, in transfer line balancing, tasks are grouped into blocks. All tasks of each block are executed simultaneously (in parallel) by one piece of equipment (spindle head). For the transfer lines considered in this paper, spindle heads at each station are activated in serial-parallel order. The set of all available spindle heads is known beforehand. Precedence, cycle time, compatibility, and parallelism constraints for the blocks and tasks are given. The line investment cost is estimated by the sum of block and station costs. The problem is to assign all tasks (using the available blocks) such that all constraints are respected and line investment cost is at a minimum. This paper focuses on solving the problem via a branch-and-bound algorithm. An approach for obtaining an efficient lower bound is offered, based on a reduction of the initial problem to a set partitioning problem. Computational experiments reveal that the proposed approach is efficient mathematically and can be used to solve practical transfer line design problems of a medium size.     

混流装配线平衡问题的多目标优化方法研究

针对混流装配线存在的工序作业多、平衡难度大等问题,以U型布置的混装线为研究对象,兼顾工作站平均负荷和瞬时负荷平衡,在最小化工作站数的基础上均衡了工作站间和工作站内不同产品的作业负荷,建立U型混流装配线多目标平衡优化模型,同时提出目标法解决联合目标中的目标函数兼容性问题。设计并运用改进的自适应遗传算法求解模型,考虑到交叉、变异操作的随机性,在变异阶段加入强制规则,并对新生成的子代个体进行基因冲突检测,以提高可行解的比率。算例研究的结果表明本文所提的多目标优化方法能够较好地解决混装线平衡问题。     

Robust balancing of straight assembly lines with interval task times

This paper addresses the balancing problem for straight assembly lines where task times are not known exactly but given by intervals of their possible values. The objective is to assign the tasks to workstations minimizing the number of workstations while respecting precedence and cycle-time constraints. An adaptable robust optimization model is proposed to hedge against the worst-case scenario for task times. To find the optimal solution(s), a breadth-first search procedure is developed and evaluated on benchmark instances. The results obtained are analysed and some practical recommendations are given.     

A Decomposition Method for Transfer Line Life Cycle Cost Optimisation

A new method to search best parameters of a transfer line so that the cost of each manufactured part will be minimised. The synchronised transfer lines with parallel machining are considered. Such lines are widely used in mass and large-scale mechanical production. The objective is to minimise the line life cycle cost per part under the given productivity and technological constraints. The design decisions to be optimised are: number of spindles and workstations. This will be accomplished by defining subsets of tasks which are performed by one spindle head and cutting conditions for each spindle. The paper focuses on a mathematical model of the problem and methods used to solve it. This model is formulated in terms of mixed (discrete and non-linear) programming and graph theory. A special decomposition scheme based on the parametric decomposition technique is proposed. For solving the sub-problems obtained after decomposition, a Branch-and-Bound algorithm as well as a shortest path technique are used.     

Flow-shop scheduling with setup and assembly operations

A scheduling model for a production system including machining, setup and assembly operations is considered. Production of a number of single-item products is ordered. Each product is made by assembling a set of several different parts. First, the parts are manufactured in a flow-shop consisting of multiple machines. Then, they are assembled into products on a single assembly stage. Setup operation and setup time are needed when a machine starts processing the parts or it changes items. The operations are partitioned into several blocks. Each block consists of the machining operations, the setup operations, and the assembly operation(s) for one or several products. The parts of the same item in a block are processed successively. The objective function is the mean completion time for all products. We consider a problem to partition the operations into blocks and sequence the parts in each block so as to minimize the objective function. Solution procedures using pseudo-dynamic programming and a branch-and-bound method are proposed. Computational experiments are carried out to evaluate the performance of the solution procedures. It has been found that a good near-optimal schedule is obtained efficiently by the proposed solution procedures.     

Equipment Location in Machining Transfer Lines with Multi-spindle Heads

The considered problem appears when a machining line must be configured. It is necessary to define the number of workstations and the number of spindle heads at each workstation to be put in the line in order to produce a given part. This problem is known to be $\mathcal{NP}$ -hard and, as a consequence, the solution time increases exponentially with the size of the problem. A number of pre-processing procedures are suggested in this article in order to decrease the initial problem size and thus shorten the solution time. A new algorithm for calculating a lower bound on the number of required equipment is also presented. A numerical example is given.     

Performance analysis of automatic assembly systems with in-line parallel stations

An automatic assembly system—a key tool for mass production—isgenerally composed of a number of workstations and a transportsystem. One common problem associated with automatic assemblysystems is that some assembly operations may have relativelylong cycle times. As a consequence, productivity, which is determinedby the operations with the longest cycle time, can be reducedsignificantly. Therefore a special form of parallel workstationknown as an in-line parallel (tandem-gated) station was developedto improve the performance of an automatic assembly system.In this design, stations working in parallel are installed ina serial structure and perform identical operations. Thus, morethan one assembly may be processed simultaneously—a typeof design especially beneficial when a stage requires a longoperation cycle time. A typical example is a computer assemblysystem which performs long inspection operations to ensure thatthe quality level of each product is up to the acceptance level. In this paper, we describe a simulation study of the performancecharacteristics of this type of system, with a statistical analysisof each decision factor. Phenomena affecting the performanceof in-line parallel stations, identified by the assistance ofthe computer graphical display, will then be discussed. An analyticalmodel based on these phenomena identified is then developed.The results generated by the analytical model developed arevalidated by comparisons with the simulation results. Finally,guidelines for optimization of buffer size are presented.     

A Hybrid Genetic Algorithm for Assembly Line Balancing

This paper presents a hybrid genetic algorithm for the simple assembly line problem, SALBP-1. The chromosome representation of the problem is based on random keys. The assignment of the operations to the workstations is based on a heuristic priority rule in which the priorities of the operations are defined by the chromosomes. A local search is used to improve the solution. The approach is tested on a set of problems taken from the literature and compared with other approaches. The computation results validate the effectiveness of the algorithm.     

A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal

The scheduling problem in a container terminal is characterized by the coordination of different types of equipment. In this paper, we present an integrated model to schedule the equipment. The objective is to minimize the makespan, or the time it takes to serve a given set of ships. The problem is formulated as a Hybrid Flow Shop Scheduling problem with precedence and Blocking constraints (HFSS-B). A tabu search algorithm is proposed to solve this problem. Certain mechanisms are developed and introduced into the algorithm to assure its quality and efficiency. The performance of the tabu search algorithm is analyzed from the computational point of view.     

A heuristic solution for fuzzy mixed-model line balancing problem

This paper addresses the mixed-model line balancing problem with fuzzy processing time. A fuzzy binary linear programming model is formulated for the problem. This fuzzy model is then transformed to a mixed zero–one program. Due to the complexity nature in handling fuzzy computation, new approximated fuzzy arithmetic operation is presented. A fuzzy heuristic is developed to solve this problem based on the aggregating fuzzy numbers and combined precedence constraints. The general idea of our approach is to arrange the jobs in a sequence by a varying-section exchange procedure. Then jobs are allocated into workstations based on these aggregated fuzzy times with the considerations of technological constraint and cycle time limit. Promising results are obtained by experiments.     

Malmquist indexes with quasi-fixed inputs: an application to school districts in Québec

We present a space and time allocation problem that arises in assembly halls producing large building blocks (namely, a shipyard which assembles prefabricated keel elements). The building blocks are very large, and, once a block is placed in the hall, it cannot be moved until all assembly operations on this block are complete. Each block must be processed during a predetermined time window. The objective is to maximize the number of building blocks produced in the hall.     

Operations planning for a multi-stage kanban system

A multi-stage production line which operates under a just-in-time production philosophy with linear demand is considered here. The first workstation processes the raw materials after receiving them from suppliers, a kanban mechanism between the workstations transports the work-in-process to the succeeding workstation, and after processing them, delivers the finished products to a buyer or a warehouse. The problem is to find optimally the number of raw material orders, kanbans circulated between workstations, finished goods shipments to the buyers, and the batch size for each shipment (lot). A cost function is developed based on the costs incurred due to the raw materials, the work-in-process between workstations, and the finished goods. Optimal number of raw material orders that minimizes the total cost is obtained, which is then used to find the optimal number of kanbans, finished goods shipments, and the batch sizes for shipments. Numerical examples are used to demonstrate the computations of optimal parameters, and to configure the kanban mechanism on a timescale. Several avenues for future research are also indicated.     

Matrix correction of a dual pair of improper linear programming problems with a block structure

The following problem is considered: how to modify the coefficient matrix of a dual pair of improper linear programs with a block structure so as to make these problems proper and minimize the sum of the squares of the Euclidean norms of the blocks in the correction matrix? Two variants of this problem are examined: (1) all the blocks in the coefficient matrix are modified, and (2) the upper block, which constraints all the primal variables, is left unchanged. Methods are presented for reducing these problems to minimizing quadratic fractional functions subject to linear equality and inequality constraints. The latter problem allows the use of conventional methods for constrained minimization. A numerical example is given.     

A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex

In this paper, we investigate the production order scheduling problem derived from the production of steel sheets in Shanghai Baoshan Iron and Steel Complex (Baosteel). A deterministic mixed integer programming (MIP) model for scheduling production orders on some critical and bottleneck operations in Baosteel is presented in which practical technological constraints have been considered. The objective is to determine the starting and ending times of production orders on corresponding operations under capacity constraints for minimizing the sum of weighted completion times of all orders. Due to large numbers of variables and constraints in the model, a decomposition solution methodology based on a synergistic combination of Lagrangian relaxation, linear programming and heuristics is developed. Unlike the commonly used method of relaxing capacity constraints, this methodology alternatively relaxes constraints coupling integer variables with continuous variables which are introduced to the objective function by Lagrangian multipliers. The Lagrangian relaxed problem can be decomposed into two sub-problems by separating continuous variables from integer ones. The sub-problem that relates to continuous variables is a linear programming problem which can be solved using standard software package OSL, while the other sub-problem is an integer programming problem which can be solved optimally by further decomposition. The subgradient optimization method is used to update Lagrangian multipliers. A production order scheduling simulation system for Baosteel is developed by embedding the above Lagrangian heuristics. Computational results for problems with up to 100 orders show that the proposed Lagrangian relaxation method is stable and can find good solutions within a reasonable time.     

The flow shop problem with no-idle constraints: A review and approximation

The makespan minimization problem in flow shops with no-idle constraints on machines is considered. The latter means that each machine, once started, must process all its operations without intermediate idle time until all those operations are completed. The problem is known to be strongly NP-hard already for three machines. While being based on a geometrical approach, we propose several polynomial time heuristics (for the general case and for special cases of 3 and 4 machines) which provide asymptotically optimal solutions for the increasing number of jobs. A comprehensive review of relevant results is also presented.     

Minimizing the Number of Tardy Jobs in a Permutation Flowshop Scheduling Problem with Setup Times and Time Lags Constraints

This paper studies the permutation flowshop scheduling problem with sequence dependent setup times and time lags constraints minimizing the number of tardy jobs. Dependent setup times are defined as the work to prepare the machines between two successive jobs. Time lags are defined as intervals of time that must exist between every couple of successive operations of the same job. Two mathematical programming formulations are proposed for the considered problem. A simulated annealing algorithm is also developed to solve the problem. Computational experiments are presented and discussed.