Flexible assembly line design problem with fixed number of workstations

In the paper, we study a flexible assembly line design problem with equipment decisions. We assume the task times and equipment costs are correlated in the sense that for all tasks the cheaper equipment gives no smaller task time. Given the cycle time and number of workstations we aim to find the assignment of tasks and equipment to the workstations so as to minimise the total equipment cost. We develop a branch and bound algorithm that uses powerful lower bounds and reduction mechanisms. Our computational experiments have revealed that our algorithm can solve large-sized problem instances in reasonable solution times.     

Bi criteria flexible assembly line design problem with equipment decisions

In this paper, we address the assembly line balancing and design problem of assigning tasks and equipment to work stations where there are several equipment alternatives for each task. We consider minimizing the total equipment cost and the number of work stations criteria. We aim to generate efficient solutions with respect to these criteria and propose a branch and bound algorithm whose efficiency is enhanced with powerful reduction and bounding mechanisms. We find that our algorithm is capable of solving problem instances with up to 25 tasks and five pieces of equipment.     

WRLSP: A Single-Machine, Warehouse Restricted Lot Scheduling Problem

This paper treats a single-machine, multi-product scheduling problem arising from an application in an automobile factory. The problem is to sequence the production lots of N products in a common cycle schedule to minimize the maximum storage space required by the machine's output, given constant production and demand rates, sequence-independent setup times and sharing of the storage space among the products. As the problem is strongly NP-hard, a heuristic and a branch and bound algorithm are developed for solving it. The algorithms are assessed on a set of random test problems similar in size and complexity to the original application.     

An order batching algorithm for wave picking in a parallel-aisle warehouse

In this paper we address the problem of batching orders in a parallel-aisle warehouse, with the objective to minimize the maximum lead time of any of the batches. This is a typical objective for a wave picking operation. Many heuristics have been suggested to solve order batching problems. We present a branch-and-bound algorithm to solve this problem exactly. An initial upper bound for the branch-and-bound algorithm is obtained using a 2-opt heuristic. We present a basic version of the algorithm and show that major improvements are obtained by a simple but very powerful preprocessing step and an improved lower bound. The improvements for the algorithm are developed and tested using a relatively small test set. Next, the improved algorithm is tested on an extensive test set. It appears that problems of moderate size can be solved to optimality in practical time, especially when the number of batches is of importance. The 2-opt heuristic appears to be very powerful, providing tight upper bounds. Therefore, a truncated branch-and-bound algorithm would suffice in practice.     

COMPARISON OF BRANCH AND BOUND AND ITERATIVE HEURISTIC ALGORITHMS FOR FLOOR ALLOCATION OF ACTIVITY CLUSTERS IN MULTISTOREY BUILDINGS

The paper presents a branch and bound algorithm and an iterative heuristic algorithm for the optimal location of clusters in a multistorey building. The use of cluster analysis is proposed for grouping highly related activities. The vertical layout problem is formulated mathematically. Results obtained by both the algorithms are compared. Some practical problems are solved and the cost comparison made     

The Segregated Storage Problem: Some Properties and an Effective Heuristic

The segregated storage problem is formulated as an integer programming problem. Some special cases are shown to reduce to ordinary assignment problems. A special property of the integer formulation is used to develop a new heuristic procedure which produces near optimal solutions and which can be used as a tight bound in branch and bound procedures. Computational comparisons with heuristics proposed by other authors indicate this method to be superior in solving large problems.     

A heuristic for setting up a flexible assembly system

We consider setup problems in flexible assembly systems (FASs) with an objective involving job priorities and station workloads. Because of the difficulty in solving the FAS setup problem, it is partitioned into two subproblems: the part type selection problem and the loading problem. We suggest a solution procedure in which branch-and-bound methods and heuristic methods are used for solving the subproblems. Part types are tentatively selected first without explicitly considering the system's restrictions, such as precedence relationships among tasks. As a result, the alternative for part type selection may not always be feasible for the loading problem. For a feasibility check and for a use in assigning tasks of selected part types, we develop an algorithm for finding a feasible sequence of the tasks. In the loading problem, tasks are assigned to stations using LPT-type rules with improvements tried through interchanging tasks. Results of computational tests on randomly generated problems are reported.     

Designing an Assembly Process with Stochastic Material Arrivals

Due to product proliferation and quick changes in manufacturing materials sourcing partnerships, assembly process in the electronic assembly industry is frequently altered or new processes are introduced. The most appropriate assembly process is critical for companies to maintain an effective supply chain. We study the problem of how to design an assembly process that relies on the stochastic arrival times of parts and components such that the probability of on-time delivery of finished products is maximized. We first provide some analytical results for cases that are polynomially solvable and then provide a branch and bound algorithm for deriving an optimal solution to the problem. We also provide heuristic algorithms to solve the problem. Finally, computational experiments show that our heuristic algorithms perform very well.     

直运越库物流的精确算法研究

多车辆直运越库调度问题的目标是最小化所有客户中的最晚到货时间.首先,建立了描述该问题的混合整数线性规划模型,并使用运筹优化工具ILOG CPLEX进行求解;其次,构造了基于LPT规则的启发式算法,为精确算法提供了初始可行解,并对分支定界算法进行详细的分析;最后,在数值实验部分,通过数学模型与分支定界的比较及算法性能的分析后,得出分支定界算法具有更高的效率,该分支定界算法在合理的时间内能够求解到11个供应商规模的问题.     

Scheduling a batch processing machine with non-identical job sizes

The problem of scheduling batch processors is important in some industries and, at a more fundamental level, captures an element of complexity common to many practical scheduling problems. We describe a branch and bound procedure applicable to a batch processor model with arbitrary job processing times, job weights and job sizes. The scheduling objective is to minimize total weighted completion time. We find that the procedure returns optimal solutions to problems of up to 25 jobs in reasonable CPU time, and can be adapted for use as a heuristic for larger problems.     

Balancing manual mixed-model assembly lines using overtime work in a demand variation environment

This study deals with the balancing problem of a manual mixed-model assembly line, where the production volume or the product mix changes from shift to shift during the planning horizon. The unstable demand can be characterised by several representative scenarios, and the line uses overtime work to meet the demand variation. The balancing problem concerns how to assign assembly tasks to stations and determine the amount of overtime in each possible demand scenario. The objective is to satisfy the demand in each possible scenario with the minimum labour costs paid for both normal shifts and overtime work. A lower bound on the labour costs is proposed, and a heuristic algorithm is developed to quickly find a feasible solution. A branch, bound and remember (BB&;R) algorithm is then proposed to find better solutions. These solution methods are tested on 765 instances. The BB&;R algorithm obtains optimal solutions for 510 instances and gives high-quality solutions for the remaining 255 instances within 60?s. The experimental results show that the use of overtime work and adjustable cycle times significantly reduces the labour costs, especially when the demand or task processing time variations are large.     

An Algorithm for the Manufacturing Equipment Selection Problem

This paper provides a unified framework in which product and process demands can be related to manufacturing system requirements. A nonlinear cost minimization model is developed that can be used by facility planners to guide the analyses underlying the equipment selection problem. The approach extends current work by accounting for machine flexibility. The objective is to determine how many of each machine type to purchase, as well as what fraction of the time each piece of equipment will be configured for a particular type of operation.

The resultant problem is solved with a depth-first branch and bound routine that employs a greedy set covering heuristic to find good feasible solutions. This permits early fathoming and greatly contributes to the efficiency of the algorithm. A small example is presented to highlight the computations. This is followed by a discussion of me results for a series of test problems designed to evaluate overall algorithmic performance. We show mat 16 process, 25 machine problems can be readily solved in less than 6 minutes on a microcomputer.     

Finding a cluster of points and the grey pattern quadratic assignment problem

In this paper we propose a model which aims at selecting a tight cluster from a set of points. The same formulation applies also to the grey pattern problem where the objective is to find a set of black dots in a rectangular grid with a given density so that the dots are spread as evenly as possible. A branch and bound algorithm and five heuristic approaches are proposed. Computational results demonstrate the efficiency of these approaches. Seven grey pattern problems are solved to optimality and for eight additional grey pattern problems the best known solution is improved. The cluster problem on a network is solved for 40 problems with the number of points ranging between 100 and 900 and the size of the cluster ranging between 5 and 200. Twenty one problems were solved optimally and the remaining 19 problems were heuristically solved in a very short computer time with excellent results.     

An Investigation of Branch and Bound Methods for Solving the Segregated Storage Problem

The segregated storage problem consists of determining a minimum cost distribution of products among compartments such that only one product may be stored in a given compartment. This paper explores the computational aspects of using branch and bound methods to solve this problem. Such methods were first suggested for this problem by White and Francis. A variety of approaches are tested, utilizing heuristic node selection and branching decision rules. Three heuristics are also presented which generate solutions for use as initial upper bounds for improving efficiency of the branch and bound procedure or as solutions for very large problems.     

Two-machine flow shop problem with unit-time operations and conflict graph

This paper addresses the problem of scheduling, on a two-machine flow shop, a set of unit-time operations subject to the constraints that some conflicting jobs cannot be scheduled simultaneously on different machines. In the context of our study, these conflicts are modelled by general graphs. The problem of minimising the maximum completion time (makespan) is known to be NP-hard in the strong sense. We propose a mixed-integer linear programming (MILP) model. Then, we develop a branch and bound algorithm based on new lower and upper bound procedures. We further provide a computer simulation to measure the performance of the proposed approaches. The computational results show that the branch and bound algorithm outperforms the MILP model and can solve instances of size up to 20,000 jobs.     

A Heuristic for a Class of Production Planning and Scheduling Problems

This paper describes a solution technique for a general class of problems referred to as aggregate planning and master scheduling problems. The technique is also applicable to multi-item single level capacitated lot sizing problems. The solution technique presented here is a heuristic that is practical for large problems e.g. 9 products and 36 periods. We have tested it for problems with varying number of time periods, number of products, setup costs, holding costs, overtime costs and capacity levels. For those problems that we could solve exactly using a branch and bound algorithm, the solutions produced by the heuristic were all within 1 % of optimality. For problems that we could not solve exactly, we are able to compute a lower bound on the optimal cost. Using the bound we are able to show that our heuristic solutions were within 2.93% of optimality on the average. Except for those problems having very high setup cost or problems with extreme seasonality, the algorithm produced solutions that were within 1 % of optimality on average.     

Scheduling jobs on unrelated parallel machines to minimize regular total cost functions

In this paper we consider unrelated parallel machine scheduling problems that involve the minimization of regular total cost functions. We first present some properties of optimal solutions and then provide a lower bound. These mechanisms are tested on the well-known practical problem of minimizing total weighted flow time on unrelated parallel machines. In doing so, we design a branch and bound algorithm incorporating the mechanisms derived for the general total cost function along with the ones derived specifically for the total weighted flow time criterion. Computational experience indicates that incoiporating reduction and bounding mechanisms significantly improves the performance of the branch and bound algorithm.     

An improved branch and bound procedure for scheduling a flow line manufacturing cell

This paper presents a new branch and bound procedure for scheduling a flow-line manufacturing cell. This procedure and an existing procedure are tested on several problem sets with varying numbers of families, jobs and machines, and varying setup time distributions. The results show that the new procedure solves small problems dramatically faster than the existing procedure. Three heuristic procedures, based on the new branch and bound procedure, are developed. These heuristic procedures as well as a tabu search procedure are tested on problem sets with larger problem sizes. The results show that one of the new procedures generates solutions with improved makespans compared to the tabu search procedure.     

A heuristic for multi-level lot-sizing problems with a bottleneck

A simple heuristic is proposed for multi-level lot-sizing problems where there is a bottleneck. Previous methods to solve this problem have formulated the problem as an integer programming problem and solved the problem using a Lagrangian relaxation embedded within the branch and bound procedure. In this paper we suggest that items to be produced can be grouped into two types and a simple but efficient heuristic can be used to determine the production quantities required. A program was developed to compute production levels and was found to require only a small fraction of the computer time required by the full integer programming approach, and to produce solutions of reasonable quality. The heuristic is simple to implement.     

Single-item production–delivery scheduling problem with stage-dependent inventory costs and due-date considerations

This paper studies an integrated scheduling problem for a single-item, make-to-order supply chain system consisting of one supplier, one capacitated transporter and one customer. Specifically, we assume the existence in the production stage of an intermediate inventory that works as a buffer to balance the production rate and the transportation speed. Jobs are first processed on a single machine in the production stage, and then delivered to the pre-specified customer by a capacitated vehicle in the delivery stage. Each job has a due date specified by the customer, and must be delivered to the customer before its due date. Moreover, it is assumed that a job that is finished before its departure date or arrives at the customer before its due date will incur a stage-dependent corresponding inventory cost (WIP inventory, finished-good inventory or customer inventory cost). The objective is to find a coordinated production and delivery schedule such that the sum of setup, delivery and inventory costs is minimised. We formulate the problem as a nonlinear model in a general way and provide some properties. We then derive a precise instance from the general model and develop a heuristic algorithm for solving this precise instance. In order to evaluate the performance of the heuristic algorithm, we propose a simple branch-and-bound (B&B) approach for small-size problems, and a lower bound based on the Lagrangian relaxation method for large-size problems. Computational experiments show that the heuristic algorithm performs well on randomly generated problems.