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.     

混合型装配线平衡问题求解方法研究

对混合型装配线平衡问题进行了描述和数学建模,提出一种启发式求解算法,求解目标是最小化工作站数目.为进一步优化求解结果,对启发式算法求解的结果进行仿真研究,分析各工作站的工作率、等待率和阻塞率,并以此为依据调整部分作业任务的分配,允许不同品种产品的相同作业任务安排在不同的工作站中,以对求解结果进行修正,进一步均衡各工作站的作业量.该求解方法既简化了求解过程,又兼顾到了系统的瞬时特性和作业任务的不可拆分性对求解结果的影响,实例分析验证了方法的有效性.     

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.     

无重叠区的双抓钩周期性排序问题的求解

在当今的自动化制造系统中，计算机控制的抓钩的排序直接影响系统的生产率。本文研究了产品在系统的一边装载、而在另一边卸载的电镀线周期性排序问题。工件在每个工作站的处理时间在给定时间范围内，工作站之间没有缓冲槽，相同轨道上的两个抓钩用于工作站之间工件的运送，目标是对运送进行排序以极小化生产周期。为了求解这个问题，本文提出一个求解方法，所提出的方法首先将生产线分为两个无重叠的区域，并且为每个区域分配一个抓钩，然后，提出了一个给定抓钩分配下的混合整数线性规划模型。通过求解不同抓钩分配下模型的最优解，并且选择这些解中最好的一个，以便得到最优解，一个标杆示例被运行，以表明该方法的应用。另外，给出有多重处理槽工序问题的模型和求解方法。     

An effective heuristic for minimising makespan on unrelated parallel machines

Scheduling independent tasks on unrelated machines is a relatively difficult and challenging problem. In this paper, we develop a tabu search based heuristic for minimising makespan for the above problem that can provide good quality solutions for practical size problems within a reasonable amount of computational time. Our adaptation of this tabu search uses hashing to control the tabu restrictions of the search process and requires fewer critical parameters than many of the common tabu search approaches employed for combinatorial optimisation. Hashing is simple to implement and very effective in providing a near-optimal solution. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.     

Solving real-life vehicle routing problems efficiently using tabu search

This paper presents a tabu search based method for finding good solutions to a real-life vehicle routing problem. The problem considered deals with some new features beyond those normally associated with the classical problems of the literature: in addition to capacity constraints for vehicles and time windows for deliveries, it takes the heterogeneous character of the fleet into account, in the sense that utilization costs are vehicle-dependent and that some accessibility restrictions have to be fulfilled. It also deals with the use of trailers. In spite of the intricacy of the problem, the proposed tabu search approach is easy to implement and can be easily adapted to many other applications. An emphasis is placed on means that have to be used to speed up the search. In a few minutes of computation on a personal workstation, our approach obtains solutions that are significantly better than those previously developed and implemented in practice.     

Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models

In this paper the multi-mode resource-constrained project scheduling problem with discounted cash flows is considered. A project is represented by an activity-on-node (AoN) network. A positive cash flow is associated with each activity. Four different payment models are considered: lump-sum payment at the completion of the project, payments at activities' completion times, payments at equal time intervals and progress payments. The objective is to maximize the net present value of all cash flows of the project. Local search metaheuristics: simulated annealing and tabu search are proposed to solve this strongly NP-hard problem. A comprehensive computational experiment is described, performed on a set of instances based on standard test problems constructed by the ProGen project generator, where, additionally, the activities' cash flows are generated randomly with the uniform distribution. The metaheuristics are computationally compared, the results are analyzed and discussed and some conclusions are given.     

Design and Evaluation of Tabu Search Algorithms for Multiprocessor Scheduling

Using a simple multiprocessor scheduling problem as a vehicle, we explore the behavior of tabu search algorithms using different tabu, local search and list management strategies. We found that random blocking of the tail of the tabu list always improved performance; but that the use of frequency-based penalties to discourage frequently selected moves did not. Hash coding without conflict resolution was an effective way to represent solutions on the tabu list. We also found that the most effective length of the tabu list depended on features of the algorithm being used, but not on the size and complexity of the problem being solved. The best combination of features included random blocking of the tabu list, tasks as tabus and a greedy local search. An algorithm using these features was found to outperform a recently published algorithm solving a similar problem.     

Simple assembly line balancing—Heuristic approaches

In this paper heuristics for Type 1 and Type 2 of the Simple Assembly Line Balancing Problem (SALBP) are described. Type 1 of SALBP (SALBP-1) consists of assigning tasks to work stations such that the number of stations is minimized for a given production rate whereas Type 2 (SALBP-2) is to maximize the production rate, or equivalently, to minimize the sum of idle times for a given number of stations. In both problem types, precedence constraints between the tasks have to be considered.We describe bidirectional and dynamic extensions to heuristic priority rules widely used for SALBP-1. For the solution of SALBP-2 we present search methods which involve the repetitive application of procedures for SALBP-1. Furthermore, improvement procedures for SALBP-2 are developed and combined with tabu search, a recent strategy to overcome local optimality. Several optional elements of tabu search are discussed. Finally, the application of a nontraditional tabu search approach to solve SALBP-1 is investigated. Computational experiments validate the effectiveness of our new approaches.     

A dispatching rule-based approach to production scheduling in a printed circuit board manufacturing system

This paper focuses on a production-scheduling problem in a printed circuit board (PCB) manufacturing system that produces multiple product types with different due dates and different manufacturing processes. In the PCB manufacturing system, there is a number of serial workstations, and there are multiple parallel machines at each workstation. Also, setup operations are required at certain workstations or machines, and some product types have re-entrant flows. We develop new dispatching rules for scheduling at each workstation, considering the special features of PCB manufacturing. With the dispatching rules, we determine not only the start time of each lot at a machine but also the batch size of each product at each machine. Simulation experiments are carried out to test the performance of the production-scheduling method and dispatching rules devised in this study. Results show that the production-scheduling method suggested in this study performs better than methods with well-known dispatching rules and heuristic algorithms for lot sizing in terms of the total tardiness of orders.     

Balancing and scheduling tasks in assembly lines with sequence-dependent setup times

The classical Simple Assembly Line Balancing Problem (SALBP) has been widely enriched over the past few years with many realistic approaches and much effort has been made to reduce the distance between the academic theory and the industrial reality. Despite this effort, the scheduling of the execution of tasks assigned to every workstation following the balancing of the assembly line has been scarcely reported in the scientific literature. This is supposed to be an operational concern that the worker should solve himself, but in several real environments, setups between tasks exist and optimal or near-optimal tasks schedules should be provided inside each workstation. The problem presented in this paper adds sequence-dependent setup time considerations to the classical SALBP in the following way: whenever a task is assigned next to another at the same workstation, a setup time must be added to compute the global workstation time. After formulating a mathematical model for this innovative problem and showing the high combinatorial nature of the problem, eight different heuristic rules and a GRASP algorithm are designed and tested for solving the problem in reasonable computational time.     

A tabu search algorithm applied to the staffing roster problem of Leicestershire police force

This paper presents an application of the tabu search algorithm to a staff rostering problem relevant to Leicestershire Police. The aim is to address the issue of structuring staff rosters to enable effective use of staff to meet the demand on the Police to reduce and deal with crime-related incidents. This problem is defined through the compilation of a time-varying level of required staff and an associated staff roster. The objective is an optimised work set-up, maximising staff resources and the meeting of demand. Optimisation of staff levels to demand is sought through use of a series of tabu search algorithms, making use of two diversification techniques and an intensification technique individually and in compilation. The tabu search is shown to be a well-suited optimisation approach to the type of problem defined, with individual conclusions drawn for each of the technique combinations used.     

Parallelizing Tabu Search on a Cluster of Heterogeneous Workstations

In this paper, we present the parallelization of tabu search on a network of workstations using PVM. Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed. The goal of parallelization is to speedup the search in finding better quality solutions. Observations support that both parallelization strategies are beneficial, with functional decomposition producing slightly better results. Experiments were conducted for the VLSI cell placement, an NP-hard problem, and the objective was to achieve the best possible solution in terms of interconnection length, timing performance (circuit speed), and area. The multiobjective nature of this problem is addressed using a fuzzy goal-based cost computation.     

A tabu search heuristic using genetic diversification for the clustered traveling salesman problem

The clustered traveling salesman problem is an extension of the classical traveling salesman problem where the set of vertices is partitioned into clusters. The objective is to find a least cost Hamiltonian cycle such that the vertices of each cluster are visited contiguously and the clusters are visited in a prespecified order. A tabu search heuristic is proposed to solve this problem. This algorithm periodically restarts its search by merging two elite solutions to form a new starting solution (in a manner reminiscent of genetic algorithms). Computational results are reported on sets of Euclidean problems with different characteristics.     

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.     

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.     

Routing and scheduling in a flexible job shop by tabu search

A hierarchical algorithm for the flexible job shop scheduling problem is described, based on the tabu search metaheuristic. Hierarchical strategies have been proposed in the literature for complex scheduling problems, and the tabu search metaheuristic, being able to cope with different memory levels, provides a natural background for the development of a hierarchical algorithm. For the case considered, a two level approach has been devised, based on the decomposition in a routing and a job shop scheduling subproblem, which is obtained by assigning each operation of each job to one among the equivalent machines. Both problems are tackled by tabu search. Coordination issues between the two hierarchical levels are considered. Unlike other hierarchical schemes, which are based on a one-way information flow, the one proposed here is based on a two-way information flow. This characteristic, together with the flexibility of local search strategies like tabu search, allows to adapt the same basic algorithm to different objective functions. Preliminary computational experience is reported.     

Parallel tabu search message-passing synchronous strategies for task scheduling under precedence constraints

This paper presents parallelization strategies for a tabu search algorithm for the task scheduling problem on heterogeneous processors under task precedence constraints. Parallelization relies exclusively on the decompostion of the solution space exploration. Four different parallel strategies are proposed and implemented on an asynchronous parallel machine under PVM: the master-slave model, with two different schemes for improved load balancing, and the single-program-multiple-data model, with single-token and multiple-token message passing schemes. The comparative analysis of these strategies shows that the tabu search approach for this problem is very suitable to the parallelization of the neighborhood search, with efficiency results almost always close to one for problems over a certain size.     

An linear programming based lower bound for the simple assembly line balancing problem

The simple assembly line balancing problem is a classical integer programming problem in operations research. A set of tasks, each one being an indivisible amount of work requiring a number of time units, must be assigned to workstations without exceeding the cycle time. We present a new lower bound, namely the LP relaxation of an integer programming formulation based on Dantzig–Wolfe decomposition. We propose a column generation algorithm to solve the formulation. Therefore, we develop a branch-and-bound algorithm to exactly solve the pricing problem. We assess the quality of the lower bound by comparing it with other lower bounds and the best-known solution of the various instances from the literature. Computational results show that the lower bound is equal to the best-known objective function value for the majority of the instances. Moreover, the new LP based lower bound is able to prove optimality for an open problem.     

A Heuristic Approach for Antenna Positioning in Cellular Networks

The antenna-positioning problem concerns finding a set of sites for antennas from a set of pre-defined candidate sites, and for each selected site, to determine the number and types of antennas, as well as the associated values for each of the antenna parameters. All these choices must satisfy a set of imperative constraints and optimize a set of objectives. This paper presents a heuristic approach for tackling this complex and highly combinatorial problem. The proposed approach is composed of three phases: a constraint-based pre-processing phase to filter out bad configurations, an optimization phase using tabu search, and a post-optimization phase to improve solutions given by tabu search. To validate the approach, computational results are presented using large and realistic data sets.