The Trended Inventory Lot Sizing Problem with Shortages Under a New Replenishment Policy

In the past few years, considerable attention has been given to the inventory lot sizing problem with trended demand over a fixed horizon. The traditional replenishment policy is to avoid shortages in the last cycle. Each of the remaining cycles starts with a replenishment and inventory is held for a certain period which is followed by a period of shortages. A new replenishment policy is to start each cycle with shortages and after a period of shortages a replenishment should be made. In this paper, we show that this new type of replenishment policy is superior to the traditional one. We further propose four heuristic procedures that follow the new replenishment policy. These are the constant demand approximation method, the equal cycle length heuristic, the extended Silver approach, and the extended least cost solution procedure. We also examine the cost and computation time performances of these heuristic procedures through an empirical study. The number of test problems solved to optimality, average and maximum cost deviation from optimum were used as measures of cost performance. The results of the 10 000 test problems reveal that the extended least cost approach is most cost effective.     

A Simulated Annealing Approach to the Solution of Flexible Labour Scheduling Problems

This paper presents a new solution approach to the discontinuous labour tour scheduling problem where the objective is to minimize the number of full-time employees required to satisfy forecast demand. Previous heuristic approaches have often limited the number of allowable tours by restricting labour scheduling flexibility in terms of shift length, shift start-times, days-off, meal-break placement, and other factors. These restrictions were essential to the tractability of the heuristic approaches but often resulted in solutions that contained a substantial amount of excess labour. In this study, we relaxed many of the restrictions on scheduling flexibility assumed in previous studies. The resulting problem environment contained more than two billion allowable tours, precluding the use of previous heuristic methods. Consequently, we developed a simulated annealing heuristic for solving the problem. An important facet of this new approach is an ‘intelligent’ improvement routine which eliminates the need for long run-times typically associated with simulated annealing algorithms. The simulated annealing framework does not rely on a special problem structure and our implementation rapidly converged to near-optimal solutions for all problems in the test environment.     

A skyline heuristic for the 2D rectangular packing and strip packing problems

In this paper, we propose a greedy heuristic for the 2D rectangular packing problem (2DRP) that represents packings using a skyline; the use of this heuristic in a simple tabu search approach outperforms the best existing approach for the 2DRP on benchmark test cases. We then make use of this 2DRP approach as a subroutine in an “iterative doubling” binary search on the height of the packing to solve the 2D rectangular strip packing problem (2DSP). This approach outperforms all existing approaches on standard benchmark test cases for the 2DSP.     

Jointly pricing and ordering for a multi-product multi-constraint newsvendor problem with supplier quantity discounts

We present an extension to the multi-product newsvendor problem by incorporating the retailer’s pricing decision as well as considering supplier quantity discount. The objective is to maximize the expected profit of the retailer through jointly determining the ordering quantities and selling prices for the products, subject to multiple capacity constraints. We formulate the problem as a Generalized Disjunctive Programming (GDP) model and develop a Lagrangian heuristic approach for its solution. Randomly produced instances involving up to 1000 products are used to test the proposed approach. Computational results show that the Lagrangian heuristic approach can present very good solutions to all instances in reasonable time.     

A hybrid tabu search/branch & bound approach to solving the generalized assignment problem

A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances.     

Routing and wavelength assignment by partition colouring

The problem of routing and wavelength assignment in all-optical networks may be solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a partition colouring problem in a conflict graph. A new tabu search heuristic is also proposed for the partition colouring problem, which may be viewed as an extension of the graph colouring problem. Computational experiments are reported, showing that the tabu search heuristic outperforms the best heuristic for partition colouring by approximately 20% in the average and illustrating that the new approach for the problem of routing and wavelength assignment is more robust than a well established heuristic for this problem.     

Another heuristic for minimizing total average cycle stock subject to practical constraints

This paper considers the setting of reorder intervals of a population of items for minimizing the total average cycle stock subject to a limit on the total number of replenishments per unit time, and a restricted set of possible intervals. Silver and Moon have investigated the problem with the use of dynamic programming, and they also proposed a heuristic for solving it. This paper presents a new 0-1 linear programming approach to the problem. Based upon the solution of the relaxed 0-1 linear programming formulation, a simple heuristic is proposed to solve the reorder problem. Limited numerical results using realistic test examples indicate that the new heuristic performed very well for each example.     

Auxiliary tool allocation in flexible manufacturing systems

This paper analyses a new approach to the machine loading problem arising in flexible manufacturing systems (FMSs). This approach allows the operations to be assigned to machines assuming that machines have access to all the tools required for their operations. This exploits the flexibility of the FMS completely. Next an allocation of tools to machines is determined which satisfies the tool requirements for each machine and minimizes the total number of tools. Thus this approach minimizes the unnecessary tool duplications in the system and maximizes the tool utilization. The problem is modeled as an integer linear program (ILP). We notice that the main problem has a block diagonal structure which is decomposable by relaxing a set of linking constraints. Each separated sub-problem represents a problem of allocation of a single type of tools. We develop a branch-and-bound based exact solution procedure and three heuristic procedures to solve the sub-problems. Our lower bounding approach uses Lanrangean relaxation. The solutions to the Lagrangean relaxation are further used to determine the branching sequences and to develop heuristic approaches. Since finding even a feasible solution to the main problem is NP-hard, we develop only enumerative procedures to solve the main problem. Finally, these solution procedures are tested on randomly generated test problems.     

Decentralised,multi-objective driven scheduling for reentrant shops: A conceptual development and a test case

This paper presents a new approach to the scheduling of reentrant shops. Its main innovative principle is an objective driven engine: jobs to be processed are selected on the basis of a balanced evaluation of how well they fulfill efficiency and effectiveness objectives. This new approach relies on a heuristic algorithm build upon a decentralised architecture, in which each production resource can act as an independent decider and selects the jobs to process according to dynamically changing criteria and to widely shared information. Interesting performances, as well as robustness and real life suitability, have been highlighted through an extensive test phase based on real data collected during two case studies, belonging to semiconductors and metalworking businesses.     

A simple dual algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The dual-type algorithm uses a simple heuristic derived from a relaxation of the problem. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach. Computational results look promising in terms of speed and solution quality.