Asia-Pacific Journal of Operational Research

∊-Sensitivity analysis (∊-SA) is a kind of method to perform sensitivity analysis for linear programming. Its main advantage is that it can be directly applied for interior-point methods with a little computation. In this paper, we discuss the property of ∊-SA analysis and its relationship with other sensitivity analysis methods. First, we present a new property of ∊-SA, from which we derive a simplified formula for finding the characteristic region of ∊-SA. Next, based on the simplified formula, we show that the characteristic region of ∊-SA includes the characteristic region of Yildirim and Todd's method. Finally, we show that the characteristic region of ∊-SA asymptotically becomes a subset of the characteristic region of sensitivity analysis using optimal partition. Our results imply that ∊-SA can be used as a practical heuristic method for approximating the characteristic region of sensitivity analysis using optimal partition.

The Vehicle Routing Problem with Backhauling deals with the supply of finished goods from a depot to a number of delivery points, and picking up returnable items and bringing them back to the depot using a fleet of trucks. Traditionally, the objective of the problem has been to determine the truck routes such that the total number of trucks and/or the total distance traveled/total route cost are minimized. Most of the papers available in the literature in this connection deal with problems where the linehaul (having a demand for finished goods) and backhaul (having items to be returned to the depot) customers are different, and a customer may be visited by at most one truck limiting demand and returns at a location by the capacity of the truck. In this paper, we allow the linehaul and backhaul customers to be the same leading to simultaneous delivery and pickup at a customer location, and also there is no restriction on the quantity demanded at (to be returned from) a customer location. As such a customer may be visited by more than one truck and more than once by the same truck. We developed a Mixed Integer Linear programming (MILP) formulation of the problem and a route construction heuristic. The heuristic averaged 80 ms for 110 problems tested, and in 78 of them the heuristic costs were either equal to the optimal costs or at most equal to the upper bounds on the optimal costs obtained after running the optimization package for 30 min. Optimal solutions were obtained for 28 problems at an average time of 295 ms. The heuristic could match the optimal solutions for 22 of these problems at an average time of 71 ms.

This article presents a new heuristic for generalized assignment problems with a very large number of jobs. The heuristic applies a probabilistic acceptance of a move, based on a percentile threshold, using information from recent moves. This percentile search heuristic (PSH) is compared to tabu search, simulated annealing, and threshold accepting using a rigorous computational experimentation with randomly generated problem instances of up to 50,000 jobs and 40 agents. The PSH did find the best solution among the heuristics for 45% of the instances, particularly larger size problems, versus 30% for tabu search, but required more fine-tuning of the heuristic parameters.

In this paper, we study an inventory system with partial backlogging, in which the backlogging rate is a continuous and nonincreasing two piece function. The total shortage cost includes three significant costs: the unit backorder cost (depending on the backorder time), the opportunity cost, and the goodwill cost. This model generalizes several inventory systems studied by other authors. The optimal policy is characterized through several results, which depend on the values of the known input parameters. Illustrative examples and a sensitivity analysis, which help us understand the theoretical results, are also given.

In this paper, we present an inventory model for deteriorating items with time varying demand and deterioration rates when the credit period depends on the retailer's ordering quantity. We also provide simple solution procedures for finding the optimal replenishment period and show in a rigorous way that the policy suggested is indeed optimal. Further, we use numerical examples to illustrate the model and conclude the paper with suggestions for possible future research.

In this paper, we investigate a semi-on-line version for a special case of three machines M₁, M₂, M₃ where the processing time of the largest job is known in advance. A speed s_i(s₁ = s₂ = 1, 1 ≤ s₃ = s) is associated with machine M_i. Our goal is to maximize the C_min — the minimum workload of three machines. We give a C_min3 algorithm and prove its competitive ratio is and the algorithm is the best possible for 1 ≤ s ≤ 2. We also claim the competitive ratio of algorithm C_min3 is tight.

We analyze a M^x/G(a,b)/1 queueing system with fast and slow service rates and multiple vacations. The server does the service with a faster rate or a slower rate based on the queue length. At a service completion epoch (or) at a vacation completion epoch if the number of customers waiting in the queue is greater than or equal to N (N > b), then the service is rendered at a faster rate, otherwise with a slower service rate. After finishing a service, if the queue length is less than 'a' the server leaves for a vacation of random length. When he returns from the vacation, if the queue length is still less than 'a' he leaves for another vacation and so on until he finally finds atleast 'a' customers waiting for service. After a service (or) a vacation, if the server finds atleast 'a' customers waiting for service say ξ, then he serves a batch of min(ξ, b) customers, where b ≥ a. We derive the probability generating function of the queue size at an arbitrary time. Various performance measures are obtained. A cost model is discussed with a numerical solution.

We propose the use of metaheuristics for the resource-capacitated multilevel lot-sizing problem with general product structures, setup costs, setup times, and lead times. Initially, we develop a heuristic which moves production in time in order to obtain feasible solutions with good quality. Strategies for the short-term memory and long-term memory of tabu search are then included to guide the search of the subordinate heuristic for new, feasible, and better solutions. Simulated annealing components are embedded into tabu search in order to improve its performance. For small problems, the solutions provided by tabu search and the hybrid metaheuristic are compared to optimal solutions and for larger problems, the quality of the solutions is evaluated against a lower bound generated by Lagrangean relaxation.