Tabu search-based algorithm for the TOC product mix decision

The theory of constraints (TOC) is a management philosophy that maximizes profits in a manufacturing plant with a demonstrated bottleneck. The product mix decision is one application of TOC that involves determination of the quantity and the identification of each product to produce. However, the original TOC heuristic is considered to produce unrealizable solution when a manufacturing plant has multiple resource constraints. This paper presents a tabu search-based TOC product mix heuristic to identify optimal or near optimal product mix for small problem instances under conditions where the original TOC heuristic failed. The tabu search-based TOC product mix heuristic is further used to solve large problem instances typical of practical manufacturing scenario. The experimental results for small to medium size problem show that the tabu search-based TOC heuristic compares favourably with those of optimal methods. Large size problems for which optimal methods have not been established in terms of feasibility in computation times were also solved in reasonable times with good quality solutions, thus confirming that the proposed approach is appropriate for adoption by production planners for the product mix problem in the manufacturing industry.     

Cyclic optimisation for localisation in freeform surface inspection

Over the last decade, several papers have been published on the contribution of the Theory of Constraints (TOC) and Throughput Accounting to product mix decisions. In these papers, the quality of the TOC-based approach to generate good or even optimal solutions is assessed with very different results, particularly when compared with other product mix decision tools. It is the objective of this article to expose the often, not explicitly revealed, premises that are mandatory for generating optimal product mix decisions using a TOC-based approach. By analysing several examples, which are modifications of one and the same basic example, premises on the solution space and the objective function are examined and conclusions made, which are shown in a checklist at the end of the paper. If more than one binding multi-product constraint occurs, optimal product mix decisions can only be derived in special cases. Also, the assumption of integer solutions may lead to non-optimal TOC-based solutions. Furthermore, a correct cost allocation is mandatory, even if sometimes not easily conductible. In particular, taking into account only (all) material costs may lead to wrong decisions. Finally, it is shown that discontinuities in the objective functions deriving, for example, from price discounts, may affect the product mix decision and require special modifications of the TOC-based approach.     

Optimizing the multiple constrained resources product mix problem using genetic algorithms

The theory of constraints (TOC) is s a management philosophy for maximizing throughput. Since its introduction, many have criticized it as being inefficient when multiple constrained resources exist. The application of the five steps contained in TOC have been criticized by some researchers on the grounds that the application of five steps of TOC to the product mix decision leads to implicit or unrealizable solutions when multiple resource constraints in a plant exist. This paper views TOC as a management philosophy and a genetic algorithm-based TOC procedure is presented for solving combinatorial problems encountered in practice which cannot be solved using linear-integer programming or similar techniques. For smaller size problems, the results of the proposed procedure are compared with results of optimal methods published in the literature. The results are encouraging and therefore support the use of the proposed approach in an industrial setting.     

Technology choice and capacity expansion with two product families: tradeoffs between scale and scope

Recent developments in modern technologies such as CIM, FMS and CAD provide a great degree of operational flexibility and permit production of a variety of products with little or no changeover costs. In contrast, dedicated technologies with specialized equipment are designed to produce a limited range of products more efficiently. In this paper, we examire the tradeoffs between scale and scope economies in a two-product environment with general, dynamic demand patterns. We use a discrete period, finite horizon mathematical program to determine the optimal mix of dedicated and flexible technologies. Since the problem is difficult to solve optimally, we develop a two-phased heuristic procedure to obtain good expansion plans that determine type of technologies and amount of capacity additions. These procedures are based on easily solvable subproblems derived from the planning problem. Our computational results suggest that the methods work well and provide acceptable solutions with reasonable effort.     

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.     

基于瓶颈的产品组合决策方法

产品组合决策关系到企业的效益。本文基于约束理论中确定瓶颈的方法,针对约束理论关于产品组合决策方法在多约束条件下的不可行性,提出了一种同时考虑主约束和最大次约束的启发式方法,分为五个步骤对其进行了详细的说明。文中还通过实例仿真来说明了新方法的可行性及简单、易用性。     

Optimal order release decisions for asynchronous production systems

Asynchronous production systems are classified into systems with fixed, unrestricted, and restricted work-in-process inventory. For each class routing optimization models are presented. Furthermore, extensions are provided in order to include optimal lotsizing and/or part mix decisions. These extensions find optimal solutions for two previously published problems with only heuristic solution procedures.     

A review and evaluation on constructive heuristics to optimise product mix based on the Theory of Constraints

In this paper, we address the problem of defining the product mix in order to maximise a system's throughput. This problem is well known for being NP-Complete and therefore, most contributions to the topic focus on developing heuristics that are able to obtain good solutions for the problem in a short CPU time. In particular, constructive heuristics are available for the problem such as that by Fredendall and Lea, and by Aryanezhad and Komijan. We propose a new constructive heuristic based on the Theory of Constraints and the Knapsack Problem. The computational results indicate that the proposed heuristic yields better results than the existing heuristic.     

A heuristic for multi-item production with seasonal demand

A heuristic is developed for a common production/inventory problem characterized by multiple products, stochastic seasonal demand, lost sales, and a constraint on overall production. Heuristics are needed since the calculation of optimal policies is impractical for real-world instances of this problem. The proposed heuristic is compared with those in current use as well as optimal solutions under a variety of conditions. The proposed heuristic is both near optimal and superior to existing heuristics. The heuristic deviated from optimality by an average of 1.7% in testing using dynamic programming as a benchmark. This compares favorably against linear-programming-based heuristics and practitioner heuristics, which deviated from optimality by 4.5 to 10.6%.     

On the optimal lot-sizing and scheduling problem in serial-type supply chain system using a time-varying lot-sizing policy

In this paper, we solve the optimal sequencing, lot-sizing and scheduling decisions for several products manufactured through several firms in a serial-type supply chain so as to minimise the sum of setup and inventory holding costs while meeting given demand from customers. We propose a three-phase heuristic to solve this NP-hard problem using a time-varying lot- sizing approach. First, based on the theoretical results, we obtain candidate sets of the production frequencies and cycle time using a junction-point heuristic. Next, we determine the production sequences for each firm using a bin-packing method. Finally, we obtain the production times of the products for each firm in the supply chain system by iteratively solving a set of linear simultaneous equations which were derived from the constraints. Then, we choose the best solution among the candidate solutions. Based on the numerical experiments, we show that the proposed three-phase heuristic efficiently obtains feasible solutions with excellent quality which is much better than the upper-bound solutions from the common cycle approach.     

Two level heuristic for the resource constrained scheduling problem

A two level heuristic for the resource constrained scheduling problem is presented. This heuristic is based on a combination of priority rules where utilization of resources by the operations, the critical path of operations in a job, and the due dates of the jobs are taken into account. The schedules that this heuristic generates have been compared with small problems for which optimal solutions are available and it is shown that these solutions are generally within 15% of the optimal. Also the polynomial time and space complexity of the heuristic is demonstrated.     

A simple lot-scheduling model for just-in-time manufacturing

In this paper we consider a single capacitated facility dedicated to the manufacturing of a set of sub-assemblies in a just-in-time (JIT) environment. The items processed on this bottleneck facility flow to a downstream assembly facility, where they are assembled according to a specified mix. We develop a simple and efficient lot-scheduling heuristic that generates feasible and least-cost manufacturing schedules for the bottleneck facility. Our heuristic was shown, through an extensive empirical comparison, to have significant advantages over an earlier proposed heuristic in the JIT literature in terms of cost performance and computational efficiency. Moreover, the results of the comparison revealed that our heuristic is more consistent with JIT objectives since it tends to generate manufacturing schedules with shorter production cycle times and fewer assemblies.     

Minimizing production flow time in a process and assembly job shop

Scheduling is one of the most important issues in the planning and operation of production systems, but in medium to large shops, the generation of consistently good schedules has proven to be extremely difficult. The problem is that optimal scheduling solutions involve costly and impractical enumeration procedures. In the literature, most scheduling problems only address jobs with serial or sequential operations. Rarely do they consider jobs in which machining and assembly operations are simultaneously involved. This lack of attention to scheduling problems that involve both machining and assembly goes against what one would normally find in most job shops. In this paper, the problem of scheduling a set of N final products on M machines in a job shop environment that involve both machining and assembly operations is addressed. The objective pursued is the minimization of production flow time (makespan). A mathematical model is developed in an effort to obtain optimal solutions. Because this type of model grows exponentially as the size of the problems increases, an heuristic solution approach is developed to solve the problems more efficiently. The models are tested and compared on several test problems.     

An improved algorithm for optimizing product mix under the theory of constraints

One of the most important decisions made in production systems is determining the product mix in such a way that maximum throughput would be obtained. Several algorithms to determine the product mix under the theory of constraints (TOC) have been developed. In this paper, the inefficiency of the traditional TOC algorithm in handling the multiple bottleneck problem is discussed through an example. Then, the latest algorithm and its disadvantages will be discussed and an improved algorithm, which is much more efficient and can reach the optimum solution with considerable speed, will be presented. Finally, the improved algorithm and the integer linear programming (ILP) method will be compared with each other through the example.     

Improving the equality of workload assignments in assembly lines

Most heuristic and optimal methods for assembly line balancing are designed either to minimize the number of workstations required given a production rate, or to maximize the production rate given a fixed number of workstations. This singular focus on line design efficiency typically results in an imbalanced allocation of tasks among the stations. This paper presents a new procedure that rebalances a given solution to level the allocation of tasks. Characteristics of dominant levelled solutions are identified and incorporated into this heuristic procedure. Computational results indicate that the procedure is very effective in levelling workloads.     

HEURISTIC APPROACHES FOR LOADING PROBLEMS IN FLEXIBLE MANUFACTURING SYSTEMS

Flexible manufacturing systems (FMSs) are able to process a wide variety of operations, but the specific mix of operations that can be performed at any point in time depends upon the combination of tools loaded onto the machines. The machines have tool magazines with finite capacities. We consider the problem of assigning operations and their associated tools to machines (or groups of machines) to maximize the throughput for a specified steady-state mix of orders. Since this objective is difficult to deal with directly, we use an intermediate objective of meeting workload targets for each machine group as closely as possible. A certain form of this intermediate objective has been shown to correlate highly with the original objective.

Since it is computationally intractable to find optimal solutions for problems with more than 20 operations, fast heuristic algorithms are developed. These algorithms are adapted from multi-dimensional bin-packing algorithms. Computational results are reported.     

Production Lot-Sizing Under Learning Effects: An Efficient Solution Technique

In this paper, we consider a production-inventory model which assumes that learning occurs as a function of the number of units produced. We analyze two cases: the first case allows for no forgetting between production runs and the second case (a generalization of the first case) allows for some given degree of forgetting between production runs. In the first case, we show that learning only has an impact on initial lot-sizes for large order quantities and that steady state lot-sizes will approach the traditional EOQ amount. In addition, we show that succeeding lot-sizes are always nonincreasing. Applying these results to the second case when forgetting occurs, we develop efficient heuristic algorithms with complexity O(N logN) to determine order quantities. Results from our algorithms are compared to optimal solutions; these comparisons indicate that our algorithms usually provide solutions within one percent of the optimal cost.     

The replacement of machines in a serially dependent multi-machine production system

In this paper a heuristic procedure is developed for solving the problem of planning machine replacements for a serially dependent production system. Given a finite planning horizon, the decision-maker wishes to decide (1) which periods, if any, that the entire production system must be shut down in order to make replacements, and (2) what specific machine or machines in the system should be scheduled for replacement during each of these downtime periods. The problem involves a balancing of costs. If the production system is brought down to make one or more replacements a fixed downtime cost is incurred; this cost is independent of the machines replaced during the downtime. In addition, other fixed coats are incurred for each of the machines replaced. Our motivation for scheduling these replacements is to realize lower variable costs for operating the machines. The variable operating costs are assumed to increase as the age or vintage of the machines increases. An optimal replacement policy is one in which the total of the present-value fixed and operating costs are minimized for the entire planning horizon. The paper also presents computational results using the heuristic to solve a large number of randomly generated test problems of varying numbers of machines and periods. These heuristic solutions are compared to known optimal solutions for a number of the problems. One of the important advantages of the heuristic procedure is that it is capable of producing several solutions to a given problem, all rank ordered by increasing cost. Thus, the decision-maker is afforded alternative choices from which he or she may select a replacement policy.     

Analysis of the type II robotic mixed-model assembly line balancing problem

In recent years, there has been an increasing trend towards using robots in production systems. Robots are used in different areas such as packaging, transportation, loading/unloading and especially assembly lines. One important step in taking advantage of robots on the assembly line is considering them while balancing the line. On the other hand, market conditions have increased the importance of mixed-model assembly lines. Therefore, in this article, the robotic mixed-model assembly line balancing problem is studied. The aim of this study is to develop a new efficient heuristic algorithm based on beam search in order to minimize the sum of cycle times over all models. In addition, mathematical models of the problem are presented for comparison. The proposed heuristic is tested on benchmark problems and compared with the optimal solutions. The results show that the algorithm is very competitive and is a promising tool for further research.     

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.