A genetic algorithm for robotic assembly line balancing

Flexibility and automation in assembly lines can be achieved by the use of robots. The robotic assembly line balancing (RALB) problem is defined for robotic assembly line, where different robots may be assigned to the assembly tasks, and each robot needs different assembly times to perform a given task, because of its capabilities and specialization. The solution to the RALB problem includes an attempt for optimal assignment of robots to line stations and a balanced distribution of work between different stations. It aims at maximizing the production rate of the line. A genetic algorithm (GA) is used to find a solution to this problem. Two different procedures for adapting the GA to the RALB problem, by assigning robots with different capabilities to workstations are introduced: a recursive assignment procedure and a consecutive assignment procedure. The results of the GA are improved by a local optimization (hill climbing) work-piece exchange procedure. Tests conducted on a set of randomly generated problems, show that the Consecutive Assignment procedure achieves, in general, better solution quality (measured by average cycle time). Further tests are conducted to determine the best combination of parameters for the GA procedure. Comparison of the GA algorithm results with a truncated Branch and Bound algorithm for the RALB problem, demonstrates that the GA gives consistently better results.     

Modelling and solving the production rate variation problem (PRVP)

Several families of objective functions for the PRV problem (minimizing the variation in the rate at which different products are produced on an assembly line) are formalized, relationships between them are established and it is demonstrated that, in very general conditions, they can be optimized by solving an assignment problem or a polynomially bounded sequence of assignment problems.     

A branch-and-bound algorithm to minimize the line length of a two-sided assembly line

A new branch-and-bound algorithm is presented to solve the two-sided assembly line balancing problem of type 1 (TALB-1). First, a pair of two directly facing station is defined as a position, and then the two-sided assembly line (TAL) is relaxed to a one-sided assembly line (OAL). Some new lower bound on positions are computed, and dominance rules and reduction rules for the one-sided assembly line balancing problem of type 1 (OALB-1) are extended and incorporated into a station-oriented assignment procedure for the TALB-1 problem. Finally, the tests are carried out on a well-known benchmark set of problem instances, and experimental results demonstrate that the proposed procedure is efficient.     

Bicriteria sequencing methods for the mixed-model assembly line in just-in-time production systems

A mixed-model manufacturing facility operating in a pull production environment can be controlled by setting a production schedule only for the last process in the facility which is usually an assembly line of mixed-model type. In the mixed-model sequencing problems, two major goals are considered: (1) smoothing the workload on each workstation on the assembly line, and (2) keeping a constant rate of usage of all parts used on the assembly line. In this study, first, some well-known solution approaches with goal 2 are analyzed through minimizing the sum-of-deviations of actual production from the desired amount. The approaches that are found to be performing better than the others are extended for the bicriteria problem considering goals 1 and 2, simultaneously. It is also shown that the bicriteria problem with the sum-of-deviations type objective function can also be formulated as an assignment problem, and the optimal solution to the small-sized problems can thus be obtained by solving the assignment problem. Finally, the conditions when it is important to take the workload-smoothing goal into consideration are analyzed.     

The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints

The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight, to satisfy operational constraints. The aim of this paper is to develop an operationally flexible method, based upon the one-day routes business model, to compute tail assignments that satisfy short-range—within the next three days—aircraft maintenance requirements. While maintenance plans commonly span multiple days, the methods used to compute tail assignments for the given plans can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by using solutions from the one-day routes aircraft maintenance routing approach as input. The daily tail assignment problem is solved with an objective to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A computational study will be performed to assess the performance of exact and heuristic solution algorithms that modify the input lines-of-flight to reduce maintenance misalignments. The daily tail assignment problem and the developed algorithms are demonstrated to compute solutions that effectively satisfy maintenance requirements when evaluated using input data collected from three different airlines.     

The Stochastic Location-Assignment Problem on a Tree

In the assignment problem units of supply are assigned on a one-to-one basis to units of demand so as to minimize the sum of the cost associated with each supply-to-demand matched pair. Defined on a network, the supplies and demands are located at vertices and the cost of a supply-to-demand matched pair is the distance between them. This paper considers a two-stage stochastic program for locating the units of supply based upon only a probabilistic characterization of demand. The objective of the first-stage location problem is to minimize the expected cost of the second-stage assignment problem. Principal results include showing that the problem is NP-hard on a general network, has a simple solution procedure on a line network, and is solvable by a low order polynomial greedy procedure on a tree network. Potential applications are discussed.     

Absalom: Balancing assembly lines with assignment restrictions

Assembly line balancing problems (ALBPs) arise whenever an assembly line is configured, redesigned or adjusted. An ALBP consists of distributing the total workload for manufacturing products among the work stations along the line. On the one hand, research has focussed on developing effective and fast solution methods for exactly solving the simple assembly line balancing problem (SALBP). On the other hand, a number of real-world extensions of SALBP have been introduced but solved with straight-forward and simple heuristics in many cases. Therefore, there is a lack of procedures for exactly solving such generalized ALBP.In this paper, we show how to extend the well-known solution procedure Salome [Scholl, A., Klein, R., 1997. Salome: A bidirectional branch-and-bound procedure for assembly line balancing. Informs J. Comput. 9 319–334], which is able to solve even large SALBP instances in a very effective manner, to a problem extension with different types of assignment restrictions (called ARALBP). The extended procedure, referred to as Absalom, employs a favorable branching scheme, an arsenal of bounding rules and a variety of logical tests using ideas from constraint programming.Computational experiments show that Absalom is a very promising exact solution approach although the additional assignment restrictions complicate the problem considerably and necessitate a relaxation of some components of Salome.     

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 vertex-face assignment for plane graphs

For every planar straight line graph (Pslg), there is a vertex-face assignment such that every vertex is assigned to at most two incident faces, and every face is assigned to all its reflex corners and one more incident vertex. Such an assignment allows us to augment every disconnected Pslg into a connected Pslg such that the degree of every vertex increases by at most two.     

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

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

Generating,scheduling and rostering of shift crew-duties: Applications at the Hong Kong International Airport

In the context of manpower planning, goal programming (GP) is extremely useful for generating shift duties of fixed length. A fixed-length duty consists of a fixed number of contiguous hours of work in a day, with a meal/rest break somewhere preferably around the middle of these working hours. It is such properties that enable the straightforward, yet flexible GP modeling. We propose GP models for an integrated problem of crew duties assignment, for baggage services section staff at the Hong Kong International Airport. The problem is solved via decomposition into its duties generating phase—a GP planner, followed by its GP scheduling and rostering phase. The results can be adopted as a good crew schedule in the sense that it is both feasible, satisfying various work conditions, and “optimal” in minimizing idle shifts.     

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.     

On a learning precedence graph concept for the automotive industry

Assembly line balancing problems (ALBP) consist in assigning the total workload for manufacturing a product to stations of an assembly line as typically applied in automotive industry. The assignment of tasks to stations is due to restrictions which can be expressed in a precedence graph. However, (automotive) manufacturers usually do not have sufficient information on their precedence graphs. As a consequence, the elaborate solution procedures for different versions of ALBP developed by more than 50 years of intensive research are often not applicable in practice.Unfortunately, the known approaches for precedence graph generation are not suitable for the conditions in the automotive industry. Therefore, we describe a new graph generation approach that is based on learning from past feasible production sequences and forms a sufficient precedence graph that guarantees feasible line balances. Computational experiments indicate that the proposed procedure is able to approximate the real precedence graph sufficiently well to detect optimal or nearly optimal solutions for a well-known benchmark data set. Even for additional large instances with up to 1,000 tasks, considerable improvements of line balances are possible. Thus, the new approach seems to be a major step to close the gap between theoretical line balancing research and practice of assembly line planning.     

Computational aspects of assigning agents to a line

We consider the problem of assigning agents to slots on a line, where only one agent can be served at a slot and each agent prefers to be served as close as possible to his target. We introduce a general approach to compute aggregate gap-minimizing assignments, as well as gap-egalitarian assignments. The approach relies on an algorithm which is shown to be faster than general purpose algorithms for the assignment problem. We also extend the approach to probabilistic assignments and explore the computational features of existing, as well as new, methods for this setting.     

Enhanced multi-Hoffmann heuristic for efficiently solving real-world assembly line balancing problems in automotive industry

In production systems of automobile manufacturers, multi-variant products are assembled on paced final assembly lines. The assignment of operations to workplaces and workers deter mines the productivity of the manufacturing process. In research, various exact and heuristic solution procedures have been developed for different versions of the so-called assembly line balancing problem.     

Optimal workforce assignment to operations of a paced assembly line

We study a paced assembly line intended for manufacturing different products. Workers with identical skills perform non-preemptable operations whose assignment to stations is known. Operations assigned to the same station are executed sequentially, and they should follow the given precedence relations. Operations assigned to different stations can be performed in parallel. The operation’s processing time depends on the number of workers performing this operation. The problem consists in assigning workers to operations such that the maximal number of workers employed simultaneously in the assembly line is minimized, the line cycle time is not exceeded and the box constraints specifying the possible number of workers for each operation are not violated. We show that the general problem is NP-hard in the strong sense, develop conventional and randomized heuristics, propose a reduction to a series of feasibility problems, present a MILP model for the feasibility problem, show relation of the feasibility problem to multi-mode project scheduling and multiprocessor scheduling, establish computational complexity of several special cases based on this relation and provide computer experiments with real and simulated data.     

A dynamic programming based heuristic for the assembly line balancing problem

The simple assembly line balancing problem is the simplification of a real problem associated to the assignment of the elementary tasks required for assembly of a product in an assembly line. This problem has been extensively studied in the literature for more than half a century. The present work proposes a new procedure to solve the problem we call Bounded Dynamic Programming. This use of the term Bounded is associated not only with the use of bounds to reduce the state space but also to the reduction of such space based on heuristics. This procedure is capable of obtaining an optimal solution rate of 267 out of 269 instances, which have been used in previous works, thus obtaining the best-known performance for the problem. These results are an improvement from any previous procedure found in the literature even when using smaller computing times.     

Two heuristic solution concepts for the vehicle selection problem in line haul transports

In this article we will develop a mathematical model for a cost-efficient selection of vehicles with varying capacities for line haul transports with leasing options. For this integer optimization problem, which is a variant of the generalized assignment problem known as NP-hard, we will compare two heuristic solution concepts and try to answer the question in which cases a user should choose an exact or approximate solution concept depending on different data instances of the problem.     

网络技术在沧州农药化工厂大检修中的应用

一、问题的提出 我厂是一个年利税超千万元的中型企业,每年都要进行一次设备大修,大修时间一般都在一个月左右.今年的检修是在企业效益比较好的情况下进行.停产检修,每天要影响上缴税利约四万元,这次检修从九月二十日开始,计划周期32天,费用七十万,主要机具电焊机的配备计划十七台.为了尽量给国家创造税利,一是需要最大限度地缩短检修时间,二是充分利用现有的机具,降低检修费用,经研究决定运用网络技术来安排这次检修.经过十七天详实地分析工艺过程,分解工序,制订实施方案,然后控制施工监督网络计划的执行,结果仅用二十一天就完成了检修任务…     

Transit passenger origin-destination estimation in congested transit networks with elastic line frequencies

This paper deals with the transit passenger origin-destination (O-D) estimation problem by using updated passenger counts in congested transit networks and outdated prior O-D matrix. A bilevel programming approach is extended for the transit passenger O-D updating problem where the upper-level problem seeks to minimize the sum of error measurements in passenger counts and O-D matrices, while the lower level is the stochastic user equilibrium assignment problem for congested transit networks. The transit assignment framework is based on a frequency-adaptive transit network model in this paper, which can help determine transit line frequencies and the network flow pattern simultaneously in congested transit networks. A heuristic solution algorithm is adapted for solving the transit passenger O-D estimation problem. Finally, a numerical example is used to illustrate the applications of the proposed model and solution algorithm. The work described in this paper was mainly supported by two research grants from the Research Grants Council of the Hong Kong Special Administrative Region (Project No. PolyU 5143/03E and PolyU 5040/02E).