Three perspectives for solving the job grouping problem

The production efficiency of printed circuit board (PCB) assembly depends strongly on the organization of the component placement jobs. This is characteristic, especially in a high-mix low-volume production environment. The present study discusses the problem of arranging the jobs of one machine into groups in such a way that the job change costs will be minimized when the costs depend on the number of the job groups. This problem is motivated by the practical case where the group utilizes a common machine set-up and the number of set-up occasions is the dominating factor in the production line optimization. The problem is well known and its large instances are hard to solve to optimality. We show how real-life problem instances can be solved by three different methods: efficient heuristics, 0/1-programming, and constraint programming. The first two of these are standard approaches in the field, whereas the application of constraint programming is new for the job grouping problem. The heuristic approach turns out to be efficient: algorithms are fast and produce optimal or nearly optimal groupings. 0/1-programming is capable of finding optimal solutions to small problem instances and it therefore serves as a benchmark to approximative methods. The constraint approach solves moderately large problem instances to optimality and it has the great advantage that changing the problem formulation is relatively easy one can add new constraints or modify the details of the existing ones flexibly.     

New Tabu search heuristics for the dynamic facility layout problem

A manufacturing facility is a dynamic system that constantly evolves due to changes such as changes in product demands, product designs, or replacement of production equipment. As a result, the dynamic facility layout problem (DFLP) considers these changes and is defined as the problem of assigning departments to locations during a multi-period planning horizon such that the sum of the material handling and re-arrangement costs is minimised. In this paper, three tabu search (TS) heuristics are presented for this problem. The first heuristic is a simple TS heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic TS heuristic. To test the performances of the heuristics, two sets of test problems from the literature are used in the analysis. The results show that the second heuristic out-performs the other proposed heuristics and the heuristics available in the literature.     

Production planning with stochastic seasonal demandand capacitated production

We consider a production/inventory problem with stochastic seasonal demand. A scarce resource limits production in each time period, and setup time is negligible. Linear and stationary costs are assessed for production, holding inventory, and stock-outs. The calculation of optimal solutions is difficult so heuristics are used. The heuristics used in business practice are shown to cost an average of 30% above optimal policy costs. A superior heuristic is constructed utilizing an analytic approximation for optimal policies that costs an average of 2% over optimal policy costs.     

Loading and sequencing heuristics for job scheduling on two unrelated parallel machines with long,sequence-dependent set-up times

The purpose of this paper is to develop and test intelligible heuristics for the scheduling of production orders that can easily be used in practice. Grounded in a case study, this paper examines the combined effects of assignment and sequencing heuristics on commonly used performance indicators. Discrete event simulation is used in the analysis to adequately capture the complexity found in the case study: production orders differing in many aspects, two unrelated parallel machines with varying and product-specific speed, and set-up times that depend on the (dis)similarity of successive orders. Evaluating 108 strategy–scenario combinations including the base case derived from the case study, it is found that a loading heuristic based on order quantity and scheduled capacity in combination with the shortest set-up heuristic performs best. When compared to the heuristic approach used by the case company, this strategy saves about 13.9% of total machine busy time and increases service level by 10.2%. In addition, using a reduced set of 40 production orders we are able to demonstrate that the best heuristic strategies comes close to results generated in a two-stage optimisation. The gap to optimality is only 3.1% in total busy time on average over all scenarios.     

A mathematical model and heuristic procedure to schedule printed circuit packs on sequencers

This paper considers the NP-hard problem of scheduling printed circuit packs (PCPs) on sequencers to minimize the total number of changeovers of input tapes required to produce PCPs. A mathematical model for this problem is given. However, when the size of the problem increases, the model will not be computationally feasible. An effective and fast heuristic to solve this problem is presented. The heuristic has shown its effectiveness over two previous heuristics found in the literature. It has been tested on a problem with 45 PCPs, two sequencers, each with seven dispensing heads, and a total of 20 input tape types. Comparison results showed that the heuristic reduced the total number of changeovers by 34% and 23% over previous heuristics. In addition, the proposed heuristic provided balanced workload across available sequencers. To investigate the efficiency of our heuristic further, we tested it against data sets from the literature. The proposed heuristic performs reasonably well compared with the reported results. In printed circuit packs' environment, set-up reduction is a main concern. Set-up is composed of the time required to changeover input tapes on sequencers when switching from PCP type to another. The proposed heuristic is more effective in reducing the number of changeovers of input tapes than heuristics found in the literature. The same heuristic can be used to schedule jobs on CNC machines so that total amount of tool switching is minimized.     

Heuristic algorithms for scheduling heat-treatment furnaces of steel casting industries

This paper addresses a research problem of scheduling parallel, non-identical batch processors in the presence of dynamic job arrivals, incompatible job-families and non-identical job sizes. We were led to this problem through a real-world application involving the scheduling of heat-treatment operations of steel casting. The scheduling of furnaces for heat-treatment of castings is of considerable interest as a large proportion of the total production time is the processing times of these operations. In view of the computational intractability of this type of problem, a few heuristic algorithms have been designed for maximizing the utilization of heat-treatment furnaces of steel casting manufacturing. Extensive computational experiments were carried out to compare the performance of the heuristics with the estimated optimal value (using the Weibull technique) and for relative effectiveness among the heuristics. Further, the computational experiments show that the heuristic algorithms proposed in this paper are capable of obtaining near (statistically estimated) optimal utilization of heat-treatment furnaces and are also capable of solving any large size real-life problems with a relatively low computational effort.     

The Multi-Product Production Cycling Problem

The multi-product production cycling problem is concerned with the determination of a production/inventory policy for a single capacitated production facility which is dedicated to producing a family of products. This paper studies this problem assuming stochastic demand. The one-product problem may be analyzed as a Markov decision problem and solved as such. For the multi-product problem, a heuristic decision rule is proposed based on the analysis of the one-product problem, and a new notion: the composite product. This heuristic is then tested by simulation on a series of problems, and is shown to be the most effective of the heuristics considered for the set of test problems     

Initial allocation compensation algorithm for redundancy allocation: The scanning heuristic

The tiny feature size in current semiconductor integrated circuits naturally requires redundancy strategies to improve manufacturing yield and operating reliability. To find an optimal redundancy architecture that provides maximum yield and reliability is a trade-off problem. In the reliability optimization field, this type of problem is generally called a redundancy allocation problem. In this paper, we propose a new iterative algorithm, the scanning heuristic, to solve the redundancy allocation problem. The solution quality of conventional iterative heuristics is highly dependent on the initial starting point of the algorithm employed. To overcome this weakness, the scanning heuristic systematically divides the original solution space into several small bounded solution spaces. The local optimum in each divided solution space then becomes a candidate for the final solution. The experimental results demonstrate that the proposed heuristic, and subsequently some combinations of heuristics, are superior to existing heuristics in terms of solution quality.     

On improving the productivity of numerically controlled punch presses

Numerically Controlled (NO) machines have in recent years revolutionized the production process, but their productivity may yet be increased by the application of new theory to the controlling computer software. This paper describes the improvement in productivity of a class of NC punch presses which operate from either an off-line computer prepared tape or under direct numerical control. The problem of tool selection and table motion during the manufacture of a product by punching an array of holes in a metal sheet with a sequence of various size and shape tools is formulated as a travelling salesman problem (TSP). Two TSP heuristics, one old and one proposed by the authors, are employed in a comparison test with the.NC press manufacturer's heuristic. Both TSP heuristics generally outperform the manufacturer's heuristic by 10% or more.     

不确定环境下的越库调度的模型及算法

研究不确定环境下的直运入厂物流调度问题。目标函数是最小化最大完工时间。供应商和客户到配送中心的运输时间的期望值和方差已知,运输时间均服从正态分布。首先研究确定性和不确定情形下的最优解差距。然后提出适用于确定和不确定情形下的带参数启发式算法,并给出面向不确定性环境的较优启发式算法,数值实验表明该算法的有效性。     

High-performing heuristics to minimize flowtime in no-idle permutation flowshop

In this article, the issue of production scheduling in a no-idle flowshop environment is addressed. An extensive literature review has shown that there are no heuristics specifically proposed for this problem, especially when it comes to constructive heuristic methods. In this context, this article proposes a highly efficient simple constructive heuristic to minimize the total flowtime criterion. The proposed heuristic was embedded in the high performance iterated greedy algorithm. Computational results and statistical analysis show that the proposed heuristic overperformed the main constructive methods found up to now. In addition, it is observed that the integration of the proposed heuristic with the iterated greedy algorithm provides the most efficient metaheuristic for the problem.     

Heuristics for the plate-cutting traveling salesman problem

In this paper we present a new problem that arises when parts are cut from large plates of metal or glass. We call this problem the plate-cutting traveling salesman problem (P-TSP) because it requires the determination of a minimum-length tour such that exactly one point must be visited on each of a number of given polygons. We present a mathematical formulation of the problem and show that the problem is a variation of the well-known traveling salesman problem. We examine the problem when the order in which parts are to be cut is known. For this problem we present a Lagrangean decomposition of the problem and develop lower bounds and heuristics based on this decomposition. Computational testing on problems with 5-40 polygons reveals that the heuristics give fairly good solutions. When the order in which polygons are to be cut is known, the heuristic solutions are within 3-4% of the optimal. The decomposition-based heuristics are embedded in a variable r-opt heuristic for the overall problem.     

A simple and effective heuristic for the resource constrained project scheduling problem

This paper investigates the development and application of a simple heuristic to the resource constrained project scheduling problem (RCPSP). This computer heuristic, which is based on the COMSOAL heuristic, constructs a feasible solution at each iteration and chooses the best solution of several iterations. Although COMSOAL was originally a solution approach for the assembly-line balancing problem, it can be extended to provide solutions to the resource allocation problem. The Modified COMSOAL technique presented in this paper uses priority schemes intermittently with a random selection technique. This hybrid of randomness and priority scheme allows a good solution to be found quickly while not being forced into the same solution at each iteration. Several different priority schemes are examined within this research. The COMSOAL heuristic modified with the priority schemes heuristic was tested on several established test sets and the solution values are compared with both known optimal values and the results of several other resource allocation heuristics. In the vast majority of cases, the Modified COMSOAL heuristic outperformed the other heuristics in terms of both average and maximum percentage difference from optimal. The Modified COMSOAL heuristic seems to have several advantages over other RCPSP heuristics in that it is easy to understand, easy to implement, and achieves good results.     

Local search for nonpreemptive multi-mode resource-constrained project scheduling

This paper addresses a general class of nonpreemptive resource-constrained project scheduling problems in which activity durations are discrete functions of committed renewable and nonrenewable resources. We provide a well known 0-1 problem formulation and stress the importance of the model by giving applications within production and operations management. Furthermore, we prove that the feasibility problem is already NP-complete. Solution procedures proposed so far have the following shortcomings: exact methods can solve only very small instances to optimality; heuristic solution approaches fail to generate feasible solutions when problems become highly resource-constrained. Hence, we propose a new local search method that first tries to find a feasible solution and secondly performs a single-neighborhood search on the set of feasible mode assignments. To evaluate the new procedure we perform a rigorous computational study on two benchmark sets. The experiment includes a comparison of our procedure with other heuristics.     

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.     

Integrating run-based preventive maintenance into the capacitated lot sizing problem with reliability constraint

A joint model for integrating run-based preventive maintenance (PM) into the capacitated lot sizing problem (CLSP) is proposed, in which the production system is subject to deterioration with usage and PM operations are implemented to restore the system. In this model, both production and PM operations are restricted by the system's maximum capacity, and the system reliability has to be maintained above a threshold value throughout the planning horizon. By linearisation of the reliability constraints, the problem is formulated as a mixed-integer linear programming. An explanatory example is given to illustrate the advantage of the joint model comparing with the interval-based PM policy in terms of system's overall cost. A three-stage heuristic is proposed to solve this integrated model, which includes a Lagrangian-based heuristic for the CLSP. The numerical experiments are conducted to evaluate the performance of the developed heuristics and the computational results show that the heuristics can provide good feasible solutions for the corresponding models. The discussion of the results is finally given in detail.     

Aggregate and detailed production planning integrating procurement and distribution plans in a multi-site environment

A monolithic mixed integer linear goal programming (MILGP) model that is developed in this paper produces a time and capacity aggregated production plan, a detailed production plan, a detailed procurement plan and a detailed distribution plan simultaneously to overcome the drawbacks of the hierarchical/sequential planning approaches of not yielding a feasible and/or an optimal plan. The model uses different time-grids and planning horizons for aggregate and detailed planning to reduce the computational burden. The limitations of storage space, raw material availability and production capacity at plants and a requirement of maintaining a minimum level of inventory buffer or forward cover have been modelled. Two heuristics that are proposed to solve the MILGP model gave good quality solutions with an average and the worse case optimality gap of 1.17% and 4.4% respectively when applied to one hundred randomly generated industry size problem instances.     

DESIGNING CELLULAR MANUFACTURING SYSTEMS: BRANCH-AND-BOUND AND A* APPROACHES

In this paper, heuristic and optimal algorithms for solving the group technology problem are presented. The heuristic algorithm is based on a branch-and-bound concept. A quadratic programming model for the machine grouping problem is formulated. The A* algorithm is developed for optimal solving of the machine grouping problem. The performance of the heuristic branch-and-bound method and the A* algorithm is compared with several existing heuristics.     

Shift scheduling for steppers in the semiconductor wafer fabrication process

In this paper, an approach is proposed for scheduling stepper machines that are acting as bottleneck machines in the semiconductor wafer fabrication process. We consider the problem of scheduling the steppers for an 8 hour shift, determining which types of wafer lots to work on each machine. The scheduling objective is to find the optimal stepper allocations such that the schedule meets target production quantities that have been derived from the given target Work-In-Process (WIP) levels. A Mixed Integer Programming (MIP) model is formulated, and three heuristic approaches are proposed and tested to approximately solve the M1P model. Numerical tests show that one of the proposed heuristics using linear programming relaxation of MIP generates, on average, schedules within 5° of the optimum values.     

A mathematical model for selecting mixed models with due dates

The performance of a sequencing procedure to smooth out the fluctuating workload (and part utilization) on a paced assembly line relies heavily on the average load of the model mixes chosen from the order-bank. Meanwhile, the due-dates of orders may conflict with this production-centred goal. This study proposes a mathematical model to select a fixed number of jobs while minimizing the total cost of producing them at the next period and satisfying capacity (RHS) limits at stations. A branch-and-bound procedure, which employs some dominance criteria, is proposed to provide optimal solutions. Pairwise interchange heuristics are developed to improve the initial solution, which is optimum but not feasible. Computational results show that optimal solutions can be obtained very efficiently for 100-job and 10-station problems. A three-factor experiment indicates that the RHS limit is the only significant parameter on the performance of the procedures. For over 1000-job problems, the best heuristic finds the optimal solution most of the time and, in the worst case, yields a solution that is 7.38% from optimality.