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.     

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 heuristic for linear sequencing of machines in layout design

This paper presents a simple heuristic to determine a common linear machine sequence for multiple products with different operation sequences and a limited number of duplicate machine types available for the job. The heuristic is based on minimisation of the total flow distance travelled by a product on the linear machine sequence. It is assumed that the flows of products are allowed only in the forward direction, either in-sequence or by-pass. It is also assumed that backtrack movements are not allowed. The effectiveness of the proposed heuristic is demonstrated through the solutions of two typical layout design problems taken from the literature. Subsequently, a number of additional problems are solved and their results are compared with the results applying existing methods. The results indicate that the proposed method can be an effective tool in solving layout design problems.     

A constrained non‐linear system approach for the solution of an extended limit analysis problem

A number of recent papers (see, e.g. (Int. J. Mech. Sci. 2007; 49 :454–465; Eur. J. Mech. A/Solids 2008; 27 :859–881; Eng. Struct. 2008; 30 :664–674; Int. J. Mech. Sci. 2009; 51 :179–191)) have shown that classical limit analysis can be extended to incorporate such important features as geometric non‐linearity, softening and various so‐called ductility constraints. The generic formulation takes the form of a challenging (nonconvex and nonsmooth) optimization problem referred to in the mathematical programming literature as a mathematical program with equilibrium constraints (MPEC). Similar to a classical limit analysis, the aim is to compute in a single step a bound (upper bound, in the case of the extended problem) to the maximum load. The solution algorithm so far proposed to solve the MPEC is to convert it into an iterative non‐linear programming problem and attempts to process this using a standard non‐linear optimizer. Motivated by the fact that no method is guaranteed to solve such MPECs and by the need to avoid the use of an optimization approach, which is unfamiliar to most practising engineers, we propose, in the present paper, a novel numerical scheme to solve the MPEC as a constrained non‐linear system of equations. We illustrate the application of this approach using the simple class of elastoplastic softening skeletal structures for which certain ductility conditions are prescribed. Copyright © 2009 John Wiley & Sons, Ltd.     

A hybrid heuristic for the multiple choice multidimensional knapsack problem

In this article, a new solution approach for the multiple choice multidimensional knapsack problem is described. The problem is a variant of the multidimensional knapsack problem where items are divided into classes, and exactly one item per class has to be chosen. Both problems are NP-hard. However, the multiple choice multidimensional knapsack problem appears to be more difficult to solve in part because of its choice constraints. Many real applications lead to very large scale multiple choice multidimensional knapsack problems that can hardly be addressed using exact algorithms. A new hybrid heuristic is proposed that embeds several new procedures for this problem. The approach is based on the resolution of linear programming relaxations of the problem and reduced problems that are obtained by fixing some variables of the problem. The solutions of these problems are used to update the global lower and upper bounds for the optimal solution value. A new strategy for defining the reduced problems is explored, together with a new family of cuts and a reformulation procedure that is used at each iteration to improve the performance of the heuristic. An extensive set of computational experiments is reported for benchmark instances from the literature and for a large set of hard instances generated randomly. The results show that the approach outperforms other state-of-the-art methods described so far, providing the best known solution for a significant number of benchmark instances.     

A Benders-based heuristic for the robust capacitated international sourcing problem

A common assumption when solving optimization problems is that all parameters are certain; however, in the real world, key data are often uncertain. In this paper, we introduce a formulation of the robust capacitated international sourcing problem. The main contribution of this work is that the formulation assumes a finite capacity, as opposed to the infinite-capacity assumption made in related studies. The formulation also deals with the uncertainty of relevant parameters, such as demand and exchange rates, and uses an objective function that incorporates a measure of risk. A heuristic search method based on Benders decomposition and tabu search is proposed and tested. The computational experiments showed that this method yields acceptable results.     

A production scheduling problem with uncertain sequence-dependent set-up times and random yield

A scheduling problem in a real production line with uncertain sequence-dependent set-up times and a random yield is considered. The production line can produce multiple product types as production lots, each of which is composed of a number of products of the same product type. To changeover product types, a sequence-dependent set-up operation should be performed, and only the lower and upper bounds are known for the sequence-dependent set-up times. Moreover, the processing time to produce the required number of product for each production lot is uncertain due to the random yield. For the objective of minimising the average tardy probability of given production lots, a systematic approximation scheme to estimate tardy probabilities of lots in any given production sequence is developed by taking not only the uncertainties but also the computational efficiency into account. As practical solution approaches, a simulated annealing and a discrete particle swarm optimisation algorithms using the approximation scheme are developed, and their performance are evaluated by computational experiments. Since there has been no research on the scheduling problems with uncertain sequence-dependent set-up times and random yield, the authors expect this research will make an excellent contribution to develop practical scheduling methodologies in uncertain scheduling environments.     

A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem

Scheduling for the flexible job-shop is a very important issue in both fields of combinatorial optimization and production operations. However, due to combination of the routing and sequencing problems, flexible job-shop scheduling problem (FJSP) presents additional difficulty than the classical job-shop scheduling problem and requires more effective algorithms. This paper developed a filtered-beam-search-based heuristic algorithm (named as HFBS) to find sub-optimal schedules within a reasonable computational time for the FJSP with multiple objectives of minimising makespan, the total workload of machines and the workload of the most loaded machine. The proposed algorithm incorporates dispatching rules based heuristics and explores intelligently the search space to avoid useless paths, which makes it possible to improve the search speed. Through computational experiments, the performance of the presented algorithm is evaluated and compared with those of existing literature and those of commonly used dispatching rules, and the results demonstrate that the proposed algorithm is an effective and practical approach for the FJSP.     

A heuristic approach to the three-dimensional cargo-loading problem

Since no exact analytical method for solving the three-dimensional cargo-loading problem has been developed, the heuristic approaches with practical assumptions are still useful. A dynamic programming approach to this problem is proposed in this paper. Loading a three-dimensional cargo space is done layer by layer, a special property which is taken advantage of in the proposed algorithm. The computational performance of this heuristic is demonstrated by comparing its results with suggested values published by the General Services Administration, Washington, DC.     

A heuristic for solving the redundancy allocation problem for multi-state series-parallel systems

The redundancy allocation problem is formulated with the objective of minimizing design cost, when the system exhibits a multi-state reliability behavior, given system-level performance constraints. When the multi-state nature of the system is considered, traditional solution methodologies are no longer valid. This study considers a multi-state series-parallel system (MSPS) with capacitated binary components that can provide different multi-state system performance levels. The different demand levels, which must be supplied during the system-operating period, result in the multi-state nature of the system. The new solution methodology offers several distinct benefits compared to traditional formulations of the MSPS redundancy allocation problem. For some systems, recognizing that different component versions yield different system performance is critical so that the overall system reliability estimation and associated design models the true system reliability behavior more realistically. The MSPS design problem, solved in this study, has been previously analyzed using genetic algorithms (GAs) and the universal generating function. The specific problem being addressed is one where there are multiple component choices, but once a component selection is made, only the same component type can be used to provide redundancy. This is the first time that the MSPS design problem has been addressed without using GAs. The heuristic offers more efficient and straightforward analyses. Solutions to three different problem types are obtained illustrating the simplicity and ease of application of the heuristic without compromising the intended optimization needs.     

A practical heuristic for the group technology economic lot scheduling problem

Automated Guided Vehicle (AGV) systems are complex to design and to implement. Inefficiencies become difficult to avoid or even to control. This paper presents the theory behind a novel agent based AGV controller that aims to control the flow of AGVs in an effective manner and, therefore, overcome the inefficiencies that can be found in complex designs. Agents are simple entities that interact with other agents to produce an emergent behaviour that is not explicitly programmed into them. The AGV controller presented uses agents as traffic managers to allow access to points and segments in the guide path. Each agent has a rule base that it uses to assess the enquiries that it receives from an AGV. Each enquiry is evaluated only at the smallest possible part of the guide path rather than the entire guide path. AGVs are then able to allocate segments and points on their paths depending on the result of each enquiry. Simulation experiments were used to test the controller and an overview is presented.     

A genetic algorithm based heuristic for adjacent paper-reel layout problem

In this paper, we present an algorithm that solves a paper reel layout problem where the available space is divided into equal-size cells. The problem is to find a layout with the minimum transportation cost subject to adjacency and other constraints. A genetic algorithm is used in a two-stage iterative approach to solve the problem. Computational results seem to indicate the efficiency and effectiveness of the proposed solution method.     

International facilities location: A heuristic procedure for the dynamic uncapacitated problem

It is now well known that most major companies no longer operate in a single market. To penetrate global markets and obtain their benefits, companies are under tremendous pressure to reduce the price of their products, and thus their production and material costs. When a foreign location is used, the components of a product are produced there and final assembly takes place either at the foreign location or at the parent domestic plant. This paper first presents the issues related to international facilities location (IFL) problems, and provides the framework required to deal with such problems. It then presents a heuristic algorithm for solving the IFL problem. Extensive computational experience was gained by solving a variety of IFL problems of different sizes.     

A dynamic programming-based heuristic for the variable sized two-dimensional bin packing problem

This paper addresses a variable sized two-dimensional bin packing problem. We propose two heuristics, H1 and H2, stemming from the dynamic programming idea by aggregating states to avoid the explosion in the number of states. These algorithms are elaborated for different purposes: H1 builds a general packing plan for items, while H2 can provide solutions by considering a variety of customer demands, such as guillotine cutting style and rotation of items. The performance of both algorithms is evaluated based on randomly generated instances reported in the literature by comparing them with the lower bounds and optimal solutions for identical bins. Computational results show that the average gaps are 8.97% and 13.41%, respectively, for H1 and H2 compared with lower bounds, and 5.26% and 6.26% compared with optimal solutions for identical bins. We also found that we can save 6.67% of space, on average, by considering variable sized bins instead of a bin packing problem with identical bins.     

A heuristic approach for a multi-product capacitated lot-sizing problem with pricing

We address a multi-product capacitated lot-sizing problem with pricing. The objective is to maximise profit. The problem extends the multi-product capacitated lot-sizing problem (CLSP) found in the literature to include price as a decision variable, demand as a function of price, setup time, and more general holding costs. We present a heuristic procedure that can be used to solve large problem instances quickly with good solution quality. The results of computational testing are presented.     

A heuristic procedure for the automobile assembly-line sequencing problem considering multiple product options

Mixed-model assembly nowadays is a common practice in the automobile industry. In an automobile assembly plant, many car options often need to be considered in sequencing an assembly line, for example, the multiple sequencing objectives that consider a pattern, blocking, spacing, and smoothing of options. A general heuristic procedure is developed in this paper for sequencing automobile assembly lines considering multiple options. The procedure obtains an initial sequence by an enhanced constructive procedure, swaps orders for the most deteriorating category of objectives, and performs re-sequencing attempting to improve the swapped sequence. The heuristic procedure was shown to frequently improve the initial sequences by swapping and re-sequencing when swapping opportunities exist. A further improvement step is also proposed to perform a limited search based on the swapped solution. The limited-search improvement step was shown to be effective in further improving solutions from the heuristic procedure in the computational experimentation. Solutions from the heuristic procedure in conjunction with the limited-search improvement step were compared to those from the simulated annealing procedure for large-size problems and showed relatively positive results.     

A simple heuristic for perishable item inventory control under non-stationary stochastic demand

In this paper, we study the single-item single-stocking location non-stationary stochastic lot sizing problem for a perishable product. We consider fixed and proportional ordering cost, holding cost and penalty cost. The item features a limited shelf life, therefore we also take into account a variable cost of disposal. We derive exact analytical expressions to determine the expected value of the inventory of different ages. We also discuss a good approximation for the case in which the shelf-life is limited. To tackle this problem, we introduce two new heuristics that extend Silver’s heuristic and compare them to an optimal Stochastic Dynamic Programming policy in the context of a numerical study. Our results demonstrate the effectiveness of our approach.     

Recursive linear control of order release to manufacturing cells with random yield

One-piece flow job shop production environments in high labor turnover environments are oftentimes characterized by late shipments and incomplete orders due to random and variable yield. The problem addressed in this paper is that of determining an order release policy for a one-piece flow prototype production line in order to meet demand in an environment subject to random and variable yield induced by high labor turnover. This paper is motivated by a problem encountered in a facility that produces prototype parts. The problem at hand can be denned as that of determining a lot size to release into the line lo minimize deviations from the demand (i.e., target batch quota) for single-piece flow production in an environment characterized by random and variable yield. The objective of this research was to investigate the utility of recursive linear control as a mechanism for releasing parts into a single-piece flow production cell, and to develop a control algorithm using a Kalman filter. The methodology is evaluated via simulation using actual demand and yield data simulated from a distribution fit from historical data. Order release strategy and yield were found to be the dominant variables for complete and on-time orders without excess and shortages, and linear recursive control was found to be effective for tracking, monitoring and adjusting the release of parts into a single-piece flow job shop in an environment characterized by random and variable yield.     

A Petri net-based heuristic for mixed-model assembly line balancing problem of Type-E

To effectively respond to the changing market demands, a manufacturer should produce variety of products with small lots. Thus, multiple products (models) are assembled simultaneously on a same line. However, it is very challenging to balance such an assembly line. This paper conducts a study on balancing a mixed-model assembly line of Type E. To solve this problem, a coloured-timed Petri net model is developed to describe the task precedence relationship. Also, the optimisation problem is formulated as a mathematical programming model. Then, with the models, a two-stage heuristic algorithm is proposed to solve the problem. At the first stage, based on the Petri net model, a P-invariant algorithm (PA) is presented to minimise the number of workstations. At the second stage, a heuristic is proposed to further minimise the cycle time by combining the PA with a binary search algorithm (BSA). Performance of the proposed method is evaluated by an illustrative example and numerical experiments. It is shown that it works well in terms of both solution accuracy and computational efficiency for large size problems.     

A simple multi-wave algorithm for the uncapacitated facility location problem

The multi-wave algorithm (Glover, 2016) integrates tabu search and strategic oscillation utilizing repeated waves (nested iterations) of constructive search or neighborhood search. We propose a simple multi-wave algorithm for solving the Uncapacitated Facility Location Problem (UFLP) to minimize the combined costs of selecting facilities to be opened and of assigning each customer to an opened facility in order to meet the customers’ demands. The objective is to minimize the overall cost including the costs of opening facilities and the costs of allocations. Our experimental tests on a standard set of benchmarks for this widely-studied class of problems show that our algorithm outperforms all previous methods.