A Modification of the Silver-Meal Heuristic to Handle MRP Purchase Discount Situations

This paper introduces an alternative approach for determining lot sizes for purchased components in MRP environments where discounts are available from vendors. This new method is a variation of the least period cost procedure, which was previously found to be a poor performer relative to the least unit cost, McLaren's order moment, and the Chung et al. procedures. The performance of this new version of the least period cost procedure, which actually is a modified version of the original Silver-Meal heuristic, is found to be excellent relative to alternative procedures. In fact, when flexibility of the method to operate in diverse environments and computational time are considered, this modified least-period cost heuristic may be the best procedure available.     

Periodic review inventory systems with a service level criterion

Full-cost inventory models are mostly studied in the literature, whereas service level constraints are more common to be observed in practical settings. In this paper, we consider periodic review inventory systems with service level restrictions. The control of such inventory systems is limited to (s, S)-type policies in the literature. To the best of our knowledge, we are the first authors to compare such policies with optimal replenishment policies, and illustrate an average cost difference of 0.64%. This justifies the use of these popular (s, S) policies in practice. Furthermore, we propose a new one-dimensional search procedure that is bounded to set the reorder level s and order-up-to level S, whereas the solution space is unbounded and two dimensional. Our heuristic procedure is guaranteed to satisfy the service level constraint and numerical experiments illustrate that it results in an average cost deviation of 1–2% compared with the best (s, S) policy. Consequently, it significantly outperforms all existing procedures from literature, both in service and costs.     

Fast heuristics for protection networks for dynamic routing

Traffic volatility and network reliability are important issues in the provision of high speed network services. We consider the construction of a second network, the protection network which can carry overload traffic due to the failure or congestion of any two links in the original network. The level of protection against such contingencies can be specified by a traffic requirement matrix. We construct a fully connected protection network, for an n node network, using an O(n²) heuristic based on the largest two traffic requirements for each node. This procedure is then modified to generate a more effective O(n⁴) heuristic, both methods facilitate fast processing for two-hop dynamic routing. We compare the performance of the heuristics with the O(n¹⁵) optimal solution.     

Minimizing the Flow-time Variance in Single-machine Systems

In this paper we deal with an n-job, single-machine scheduling problem. All jobs are available from the start, and the objective is to minimize the variance of job flow-times. A heuristic procedure which is based on the complementary pair-exchange principle is proposed. It has been concluded that this heuristic procedure provides improved results (in terms of objective-function value) when compared with other heuristics. Our heuristic procedure has the complexity of O(n log n).     

A sequential method for preventive maintenance and replacement of a repairable single-unit system

This paper is concerned with when to implement preventive maintenance (PM) and replacement for a repairable ‘single-unit’ system in use. Under the main assumption that a ‘single-unit’ system gradually deteriorates with time, a sequential method is proposed to determine an optimal PM and replacement strategy for the system based on minimising expected loss rate. According to this method, PM epochs are determined one after the other, and consequently we can make use of all previous information on the operation process of the system. Also the replacement epoch depends on the effective age of the system. A numerical example shows that the sequential method can be used to solve the PM and replacement problem of a ‘single-unit’ system efficiently. Some properties of the loss functions W(L? _n ,b? _n ) and W? _r (N) with respect to PM and replacement respectively are discussed in the appendix.     

A greedy randomised search heuristic for time-constrained vehicle scheduling and the incorporation of a learning strategy

In this paper, a greedy randomised heuristic is applied to a complex vehicle-scheduling problem with tight time windows and additional constraints. Two forms of adaptive search are identified, which are referred to as local and global adaptation. In both cases, the calculation of the greedy function is modified by an amount which measures heuristically the quality of the partial solution that is obtained when a decision is made. One use of global adaptation is an approach which is referred to as a learning strategy since it involves an attempt to learn from previous mistakes by an appropriate updating of the greedy function from one run of the heuristic to the next. Such a learning strategy forms the main focus of this paper. Experimental results show that it is potentially a powerful heuristic device, since it greatly enhanced the effectiveness of those methods that had previously been applied to this problem; that is, a greedy randomized heuristic which also incorporated a look-ahead strategy and a version of the well-known savings method. It is suggested that learning strategies of the general type introduced in this paper have potential for application to other combinatorial optimisation problems.     

A simple and effective recursive procedure for the manufacturer's pallet loading problem

In this paper we present a simple and effective heuristic to solve the problem of packing the maximum number of rectangles of sizes (l,w) and (w,l) into a larger rectangle (L,W) without overlapping. This problem appears in the loading of identical boxes on pallets, namely the manufacturer's pallet loading (MPL), as well as in package design and truck or rail car loading. Although apparently easy to be optimally solved, the MPL is claimed to be NP-complete and several authors have proposed approximate methods to deal with it. The procedure described in the present paper can be seen as a refinement of Bischoff and Dowsland's heuristic and can easily be implemented on a microcomputer. Using moderate computational resources, the procedure was able to find the optimal solution of 99.9% of more than 20?000 examples analysed.     

Minimizing the sum of maximum earliness and maximum tardiness in the single-machine scheduling problem with sequence-dependent setup time

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize the sum of maximum earliness and maximum tardiness when sequence-dependent setup times exist (1∣ST _sd ∣ET_max). In this paper, an optimal branch-and-bound algorithm is developed that involves the implementation of lower and upper bounding procedures as well as three dominance rules. For solving problems containing large numbers of jobs, a polynomial time-bounded heuristic algorithm is also proposed. Computational experiments demonstrate the effectiveness of the bounding and dominance rules in achieving optimal solutions in more than 97% of the instances.     

An Optimal Heuristic For Coordinated Multi-Item Inventory Replenishments

The inventory control problem can be vastly simplified if the replenishments of inventory items are coordinated with one another. That is, whenever an item is replenished, n other items, where n is a decision variable, are also replenished. One way to ensure this would be to classify the inventory items into several groups with a common order interval for each group. In this paper we establish that the optimal groups will be consecutive by hD/A, where h, D and A are the holding cost, demand rate and set-up cost of an item respectively. Using this property of consecutiveness, we develop a fast converging heuristic to create m groups optimally, m = 2, 3,..., M. The heuristic is a substitute for the dynamic programme which would otherwise be necessary and it has the potential for nomographic applications.     

A note on parallel-machine due-window assignment

We consider a due-window assignment problem on identical parallel machines, where the jobs have equal processing times and job-dependent earliness-tardiness costs. We would like to determine a ‘due window’ during which the jobs can be completed at no cost and to obtain a job schedule in which the jobs are penalized if they finish before or after the due window. The objective is to minimize the total earliness and tardiness job penalty, plus the cost associated with the size of the due window. We present an algorithm that can solve this problem in O(n³) time, which is an improvement of the O(n⁴) solution procedure developed by Mosheiov and Sarig.     

Optimal project selection: Stochastic knapsack with finite time horizon

A time-constrained capital-budgeting problem arises when projects, which can contribute to achieving a desired target state before a specified deadline, arrive sequentially. We model such problems by treating projects as randomly arriving requests, each with a funding cost, a proposed benefit, and a known probability of success. The problem is to allocate a non-renewable initial budget to projects over time so as to maximise the expected benefit obtained by a certain time, T, called the deadline, where T can be either a constant or a random variable. Each project must be accepted or rejected as soon as it arrives. We developed a stochastic dynamic programming formulation and solution of this problem, showing that the optimal strategy is to dynamically determine ‘acceptance intervals’ such that a project of type i is accepted when, and only when, it arrives during an acceptance interval for projects of type i.     

Heuristic procedures for the single facility inspection problem with minimal repair and increasing failure rate

This paper presents the problem of setting inspection schedules for a single imperfect facility undergoing minimal repair once detected in an ‘out-of-control’ state. The problem is modelled under a non-Markovian failure mechanism with increasing failure rate. We show that the profit maximization formulation of the problem is equivalent to the cost minimization formulation and concentrate on the latter. We then develop three heuristic procedures that are shown to be very cost effective based on the results of the numerical examples used for illustration.     

A structural model for sales in the e-retailing industry

This article analyses intangible constructs that affect sales on the Internetretailing industry. We suggest an explanatory model for the success of retailersthat operate on the Internet. Non-financial information has been used toidentify several intangible constructs: ‘web trafficgeneration’, ‘relevance in search engines’,‘link popularity’, and ‘blogspopularity’. The success is measured through items derived fromfinancial statements: sales and profits. The model has been built within astructural modelling framework. It has been estimated using Partial LeastSquares with a sample of USA e-tailers. The results show that there is asignificant relationship between the intangible constructs and accountingfigures. This relationship is stronger when we consider Sales from InternetOperations rather than Total Sales or Net Profit.     

Reorder quantities for (<Emphasis Type="Italic">Q,R</Emphasis>) inventory models

The reorder level R and the reorder quantity Q are the parameters to be decided in a continuous review inventory policy. Their optimal values can be approached through iterative methods, but these are tedious and inconvenient for control routines. A frequent practice is to set Q as the economic reorder quantity and compute R accordingly. Yet this practice may introduce a substantial cost penalty. The paper re-arranges conventional theoretical expressions in order to facilitate the use of numerical approximations to help find a quasi-optimal solution. This approach is then applied to Gamma distributed demands showing that computations are straightforward.     

Heuristic Solution Methods for Two Location Problems with Unreliable Facilities

In this paper, the p-median and p-centre problems are generalized by considering the possibility that one or more of the facilities may become inactive. The unreliable p-median problem is defined by introducing the probability that a facility becomes inactive. The (p, q)-centre problem is defined when p facilities need to be located but up to q of them may become unavailable at the same time. An heuristic procedure is presented for each problem. A rigorous procedure is discussed for the (p, q)-centre problem. Computational results are presented.     

Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic

The uncapacitated facility location problem (UFLP) is a popular combinatorial optimization problem with practical applications in different areas, from logistics to telecommunication networks. While most of the existing work in the literature focuses on minimizing total cost for the deterministic version of the problem, some degree of uncertainty (e.g., in the customers’ demands or in the service costs) should be expected in real-life applications. Accordingly, this paper proposes a simheuristic algorithm for solving the stochastic UFLP (SUFLP), where optimization goals other than the minimum expected cost can be considered. The development of this simheuristic is structured in three stages: (i) first, an extremely fast savings-based heuristic is introduced; (ii) next, the heuristic is integrated into a metaheuristic framework, and the resulting algorithm is tested against the optimal values for the UFLP; and (iii) finally, the algorithm is extended by integrating it with simulation techniques, and the resulting simheuristic is employed to solve the SUFLP. Some numerical experiments contribute to illustrate the potential uses of each of these solving methods, depending on the version of the problem (deterministic or stochastic) as well as on whether or not a real-time solution is required.     

Containment of socially optimal policies in multiple-facility Markovian queueing systems

We consider a Markovian queueing system with N heterogeneous service facilities, each of which has multiple servers available, linear holding costs, a fixed value of service and a first-come-first-serve queue discipline. Customers arriving in the system can be either rejected or sent to one of the N facilities. Two different types of control policies are considered, which we refer to as ‘selfishly optimal’ and ‘socially optimal’. We prove the equivalence of two different Markov Decision Process formulations, and then show that classical M/M/1 queue results from the early literature on behavioural queueing theory can be generalized to multiple dimensions in an elegant way. In particular, the state space of the continuous-time Markov process induced by a socially optimal policy is contained within that of the selfishly optimal policy. We also show that this result holds when customers are divided into an arbitrary number of heterogeneous classes, provided that the service rates remain non-discriminatory.     

A Maintenance Model with Opportunities and Interrupt Replacement Options

A component has time to failure X with density f(·). Opportunities arise as a Poisson process of rate λ. At an opportunity the component may at choice, be replaced at cost c₂. At failure the components can either be minimally repaired at cost c₁ or replaced at cost c₄. Finally the component may be replaced at any time at an ‘interrupt’ cost of c₃. We derive expressions for the long-run expected cost rate, and give examples of numerical optimisation with respect to control limits on age at an opportunity, and at an interrupt replacement.     

Optimal strategy in <Emphasis Type="Italic">N</Emphasis>-policy production system with early set-up

This paper considers a production system in which an early set-up is possible. The machine(server) is turned off when there are no units(customers) to process. When the accumulated number of units reaches m(<N), the operator starts a set-up that takes a random time. After the set-up, if there are N or more units waiting for processing, the machine begins to process the units immediately. Otherwise the machine remains dormant in the system until the accumulated number of units reaches N. We model this system by M/G/1 queue with early set-up and N-policy. We use the decomposition property of a vacation queue to derive the distribution of the number of units in the system. We, then, build a cost model and develop a procedure to find the optimal values of (m,N) that minimize a linear average cost.     

Economic design of an adaptive <Emphasis Type="Italic">T</Emphasis><Superscript>2</Superscript> control chart

Varying three parameters of the Hotelling's T² control chart, namely, the sample size, the sampling interval length, and the action limit, results in a great improvement over the traditional T² control chart particularly for the small process shift. This paper presents the economic model for designing the variable parameters T² chart. In the economic design, a cost function is constructed, involving the cost of sampling and testing, the cost of false alarm, the cost to detect and remove the assignable cause, and the cost when the process is operating out-of-control. Also, a heuristic method of finding optimal values of adaptive design parameters for minimizing the cost function is presented. Variable and fixed parameters T² control charts are compared with respect to the expected loss per unit time. Furthermore, the effects of the initial sample number (used for estimating the parameters of F-distribution) upon the operating cost and adaptive design parameters are examined.