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.     

State-of-the-art exact and heuristic solution procedures for simple assembly line balancing

The assembly line balancing problem arises and has to be solved when an assembly line has to be configured or redesigned. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line. The so-called simple assembly line balancing problem (SALBP), a basic version of the general problem, has attracted attention of researchers and practitioners of operations research for almost half a century.In this paper, we give an up-to-date and comprehensive survey of SALBP research with a special emphasis on recent outstanding and guiding contributions to the field.     

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

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

A survey on problems and methods in generalized assembly line balancing

Assembly lines are traditional and still attractive means of mass and large-scale series production. Since the early times of Henry Ford several developments took place which changed assembly lines from strictly paced and straight single-model lines to more flexible systems including, among others, lines with parallel work stations or tasks, customer-oriented mixed-model and multi-model lines, U-shaped lines as well as unpaced lines with intermediate buffers.In any case, an important decision problem, called assembly line balancing problem, arises and has to be solved when (re-) configuring an assembly line. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line.Assembly line balancing research has traditionally focused on the simple assembly line balancing problem (SALBP) which has some restricting assumptions. Recently, a lot of research work has been done in order to describe and solve more realistic generalized problems (GALBP). In this paper, we survey the developments in GALBP research.     

Metaheuristic algorithms for balancing robotic assembly lines with sequence-dependent robot setup times

Industries are incorporating robots into assembly lines due to their greater flexibility and reduced costs. Most of the reported studies did not consider scheduling of tasks or the sequence-dependent setup times in an assembly line, which cannot be neglected in a real-world scenario. This paper presents a study on robotic assembly line balancing, with the aim of minimizing cycle time by considering sequence-dependent setup times. A mathematical model for the problem is formulated and CPLEX solver is utilized to solve small-sized problems. A recently developed metaheuristic Migrating Birds Optimization (MBO) algorithm and set of metaheuristics have been implemented to solve the problem. Three different scenarios are tested (with no setup time, and low and high setup times). The comparative experimental study demonstrates that the performance of the MBO algorithm is superior for the tested datasets. The outcomes of this study can help production managers improve their production system in order to perform the assembly tasks with high levels of efficiency and quality.     

Dynamic task assignment for throughput maximization with worksharing

The traditional assembly line balancing problem involves assigning a set of partially precedence constrained tasks to workstations to maximize efficiency. Each task is assigned to a unique workstation. The case is considered where task sequences are known but the workforce is partially cross-trained and some tasks can alternate between workstations. The flexibility afforded by cross-training allows the line balance to improve. Task times are allowed to be random and small buffers are allowed between workstations. Decision rules are developed and tested for various levels of cross-training between adjacent workers. Cross-training is shown to have significant impact on throughput and easy to administer rules are proven to be effective. The number of decision points for deciding to hold or pass a unit of product is also shown to be important.     

Weekly staff scheduling with workstation group restrictions

This paper addresses the weekly adjustment problem for staff scheduling when movement restrictions exist between workstation groups (WSGs). In practice, it is common for employees to be organized into physical or logical groups to match the layout of a facility or to facilitate managerial oversight. A complication in the problem arises when each employee is required to spend more time at his or her assigned home base during the week than at any other WSG. This conflicts with a common strategy of reassigning employees to different WSGs when idle time exists in their schedules. Ordinarily, the full problem is tackled with a two-phase approach, where optimal shifts and overtime allocations are first derived and then tasks are assigned. When movement restrictions exist in a facility, this approach is no longer practical or even possible for all but the smallest instances. Alternatively, a new model is proposed that integrates WSG restrictions with the shift scheduling and task assignment constraints. The model takes the form of a large-scale integer program and is solved with one of two decomposition heuristics. The first splits the movement restrictions network into manageable pieces; the second uses column generation to identify good individual schedules that are used to construct a set-covering-type master problem. A solution to the master problem provides a feasible solution to the original integer program. Extensive testing was done with data obtained from the U.S. Postal Service mail processing and distribution center in Dallas. The results show that good feasible solutions can be obtained in less than an hour.     

Tabu search algorithms for an industrial multi-product and multi-objective assembly line balancing problem,with reduction of the task dispersion

This paper presents a real-world industrial application of the multi-product and multi-objective assembly line balancing problem, for a company involved in the production of four models of a white goods product. The problem solved is a GALBP-2, with 10 workstations and multiple objectives (to maximize the production rate in order to deal with an increase of the demand forecasted, to reach an equal cycle time of all the models and an equal workload of the different workstations, and finally, to minimize the dispersion of worker tasks on each one of the different models—the common tasks of the different models at the same workstation). The paper presents an integrated approach based on four heuristics cited in the literature and: (1) an improvement procedure based on tabu search, with the objective of minimizing the cycle time; and, subsequently, (2) a second tabu search in order to increase the uniformity of the tasks performed at each workstation (the common tasks at the same workstation).     

SUSTAINABLE YIELDS IN FISHERIES: UNCERTAINTY,RISK‐AVERSION,AND MEAN‐VARIANCE ANALYSIS

Abstract We consider a model of a fishery in which the dynamics of the unharvested fish population are given by the stochastic logistic growth equation Similar to the classical deterministic analogon, we assume that the fishery harvests the fish population following a constant effort strategy. In the first step, we derive the effort level that leads to maximum expected sustainable yield, which is understood as the expectation of the equilibrium distribution of the stochastic dynamics. This replaces the nonzero fixed point in the classical deterministic setup. In the second step, we assume that the fishery is risk averse and that there is a tradeoff between expected sustainable yield and uncertainty measured in terms of the variance of the equilibrium distribution. We derive the optimal constant effort harvesting strategy for this problem. In the final step, we consider an approach that we call the mean‐variance analysis to sustainable fisheries. Similar as in the now classical mean‐variance analysis in finance, going back to Markowitz [1952] , we study the problem of maximizing expected sustainable yields under variance constraints, and with this, minimizing the variance, e.g., risk, under guaranteed minimum expected sustainable yields. We derive explicit formulas for the optimal fishing effort in all four problems considered and study the effects of uncertainty, risk aversion, and mean reversion speed on fishing efforts.     

The wafer probing scheduling problem (WPSP)

The wafer probing scheduling problem (WPSP) is a variation of the parallel-machine scheduling problem, which has many real-world applications, particularly, in the integrated circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which must be processed on groups of identical parallel machines and be completed before the due dates. Further, the job processing time depends on the product type, and the machine setup time is sequence dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequence dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this paper, we formulate the WPSP as an integer programming problem. We also transform the WPSP into the vehicle routing problem with time windows (VRPTW), a well-known network routing problem which has been investigated extensively. An illustrative example is given to demonstrate the proposed transformation. Based on the provided transformation, we present three efficient algorithms to solve the WPSP near-optimally.     

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.     

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.     

A variable neighbourhood search algorithm for the constrained task allocation problem

A variable neighbourhood search algorithm that employs new neighbourhoods is proposed for solving a task allocation problem whose main characteristics are: (i) each task requires a certain amount of resources and each processor has a capacity constraint which limits the total resource of the tasks that are assigned to it; (ii) the cost of solution includes fixed costs when using processors, task assignment costs, and communication costs between tasks assigned to different processors. A computational study shows that the algorithm performs well in terms of time and solution quality relative to other local search procedures that have been proposed.     

Audit scheduling with overlapping activities and sequence-dependent setup costs

Audit firms are faced with the complex job of scheduling auditors to audit tasks. The scheduling becomes more complex as the firm needs to consider real life issues in determining an optimal schedule. Among these issues are the setup times and costs emanating from changing the assignments of the auditors and the lead and lag relationships between the audit tasks.Audit scheduling with overlapping activities and sequence-dependent setup cost has not been treated in literature. This paper presents a formulation and a solution approach for this audit scheduling problem. First, the problem is represented by an activity network with lead/lag relationships. Then the network is analyzed to determine the early and late finish times of activities. An integer linear program (ILP), which uses the early and late finish times of activities to reduce the number of decision variables, is formulated. A four-auditor two-engagement example is used to illustrate the ILP model and its solution. The results indicate that incorporating the setup cost and the overlapping of activities yields lower cost schedules leading to sizable savings in the cost of audits. The proposed treatment is of merit in providing realistic schedules that can be easily implemented     

Batching deteriorating items with applications in computer communication and reverse logistics

We study two deterministic scheduling problems that combine batching and deterioration features. In both problems, there is a certain demand for identical good quality items to be produced in batches. In the first problem, each batch is assigned an individual machine that requires a cost and a time to be activated. All the machines are identical, work in parallel, and always produce good quality items. All the items are available at time zero and they deteriorate while waiting for production. Deterioration results in a linear increase of time and cost of production. In the second problem, there is a single machine that produces good quality as well as defective items in batches. Each batch is preceded by a setup time and requires a setup cost. Defective items have to be reworked on the same machine. They deteriorate while waiting for rework. At a time to be decided, the machine switches from production to rework defective items of the current batch. After rework, every defective item has the required good quality. In both problems, the objective is to find batch partitioning such that a linear combination of the production cost and production completion time is minimized. The two problems are observed at computer service providers and also reverse logistics. In computer service providers, machines and items correspond to communication service channels and information transfer tasks, respectively. We reduce both problems to minimizing a function of one variable representing the number of batches. In an optimal solution of either problem, there are at most two different batch sizes. Linear time algorithms are proposed for both problems.     

Parallel machine scheduling with a learning effect

The phenomenon of ‘learning’ has been extensively studied in many different areas of Operational Research. However, the ‘learning effect’ of the producer/processor has rarely been studied in the general context of production scheduling, and has never been investigated in multi-machine scheduling settings. We focus in this paper on flow-time minimization on parallel identical machines. We show that this problem has a polynomial time solution, although the computational effort required is much larger than the effort required for solving the classical version of the problem.     

Simple and U-type assembly line balancing problems with a learning effect

In this paper, we introduced learning effect into assembly line balancing problems. In many realistic settings, the produced worker(s) (or machine(s)) develops continuously by repeated the same or similar activities. Therefore, the production time of product shortens if it is processed later. We show that polynomial solutions can be obtained for both simple assembly line balancing problem (SALBP) and U-type line balancing problem (ULBP) with learning effect.     

Marketing-production decisions under independent and integrated channel structure

The topic of channel structure has recently attracted much attention among researchers in the marketing and economics area. However, in a majority of the existing literature the cost considerations are extremely simplified with the major focus being pricing policy. What happens when cost incurring decisions are strongly connected with pricing policies? This is the theme we wish to explore in the present paper. The non-trivial costs considered are production, inventory, and retailer effort rate, i.e. we seek to explore the marketing-production channel. We have used the methodology of differential games. The open-loop Stackelberg solution concept has been used to solve the manufacturer and retailer's problem. The Pareto solution concept has been used to solve the problem of the vertically integrated firm. The production, pricing, and effort rate policies thus derived have been compared to obtain insights into the impact of channel structure on these policies. Also, to examine the relation between channel structure and the retailing operation requiring effort, we derive the Stackelberg and Pareto solutions with and without effort rate as a decision variable. We show that once the production rate becomes positive, it does not become zero again. This implies production smoothing. However, none of the gains of production smoothing are passed on to the retailer. The optimal production rate and the inventory policy are a linear combination of the nominal demand rate, the peak demand factor, the salvage value, and the initial inventory. Also, as opposed to some of the existing literature, the optimal policies need not necessarily be concave in nature. In the scenario where the relating operation does not require effort, the pricing policies of the manufacturer and the retailer, and the production policy of the manufacturer have a synergistic effect. However, in the scenario where the retailing operation does benefit from effort, the retailer's pricing policy need not necessarily be synergistic with other policies. With regard to channel structures, it seems that production smoothing will be done more efficiently in the integrated setup. Also, we show that the price paid by the consumer need not necessarily be lower in the integrated setup. But despite higher prices, the channel profits are higher in the integrated setup. This implies a conflict between the interests of the consumers and the firm. Also, this contradicts the results of some of the earlier papers that have used simple static models.     

Multi-criteria assignment problem with incompatibility and capacity constraints

The considered assignment problem generalizes its classical counterpart by the existence of some incompatibility constraints limiting the assignment of tasks to processing units within groups of mutually exclusive tasks. The groups are defined for each processing unit and the constraints allow at most one task from each group to be assigned to the corresponding processing unit. The processing units can normally process a certain number of tasks without any cost; this capacity can be extended, however, at some extra marginal cost that is non-decreasing with the number of additional tasks. Each task has to be assigned to exactly one processing unit and has some preference for the assignment; it is expressed for each pair ‘task-processing unit’ by a dissatisfaction degree. The quality of feasible assignments is evaluated by three criteria: g ₁-the maximum dissatisfaction of tasks, g ₂-the total dissatisfaction of tasks, g ₃-the total cost of processing units. If there is no feasible assignment, tasks and processing units creating a blocking configuration are identified and all actions of unblocking are proposed. Formal properties of blocking configurations and unblocking actions are proven, and an interactive procedure for exploring the set of non-dominated assignments is described together with illustrative examples processed by special software.     

多机排序问题pm｜fix_j，pmtn｜C_（max）的多项式时间算法

在经典排序论中，一般都作以下两条假设：其一是每台机器在任一时刻至多加工一个零件，其二是每个零件在任一时刻至多被一台机器加工．在这篇文章中，研究多台机器可同时加工一个零件的多机排序问题，且每个零件可在固定的一个机器的子集上加工．本文在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究了这种问题的计算复杂性．