A spanning heuristic for the unordered and ordered matching identification problem

The matching identification problem (MIP) is a combinatoric search problem related to the fields of learning from examples, boolean functions, and knowledge acquisition. The MIP involves identifying a single “goal” item from a large set of items. Because there is commonly a cost associated with evaluating each guess, the goal item should be identified in as few guesses as possible. As in most search problems, the items have a similar structure, which allows an evaluation of each guessed item. In other words, each guessed item elicits partial information about the goal item, i.e. how similar the guess is to the goal. With this information the goal is more quickly identified.The unordered MIP has been studied by Mehrez and Steinberg (ORSA J. Comput. 7 (1995) 211) in which they proposed two different types of algorithms. The purpose of the present paper is to suggest an improved Spanning Heuristic algorithm. Its improvement increases as the problem size increases. Further results and comparisons are derived for the unordered and ordered cases.This research shows that when the search space is very large, it is better to inquire from items that are known not to be the goal (they have been ruled out by previous guesses), for the purpose of acquiring more information about the goal. As the search space is narrowed, it is better to guess items that have not been ruled out.     

Minimization of passenger takeoff and landing risk in offshore helicopter transportation: Models,approaches and analysis

Offshore petroleum industry uses helicopters to transport the employees to and from installations. Takeoff and landing represent a substantial part of the flight risks for passengers. In this paper, we propose and analyze approaches to create a safe flight schedule to perform pickup of employees by several independent flights. Two scenarios are considered. Under the non-split scenario, exactly one visit is allowed to each installation. Under the split scenario, the pickup demand of an installation can be split between several flights. Interesting links between our problem and other problems of combinatorial optimization, e.g., parallel machine scheduling and bin-packing are established. We provide worst-case analysis of the performance of some of our algorithms and report the results of computational experiments conducted on randomly generated instances based on the real sets of installations in the oil fields on the Norwegian continental shelf. This paper is the first attempt to handle takeoff and landing risk in a flight schedule that consists of several flights and lays ground for the study on more advanced and practically relevant models.     

Unraveling quantity discounts

We consider the situation in which a buying organization deals with a discrete quantity discount schedule offered by a selling organization. Furthermore, the buying organization can negotiate with the selling organization about the lot size and purchase price, but does not know the underlying function that was used by the selling organization to determine the quantity discount schedule. In this paper, we provide an analytical and empirical basis for one general quantity discount function (QDF) that can be used to describe the underlying function of almost all different quantity discount types. We first develop such a QDF analytically. Among other things, this QDF enables buying organizations to calculate detailed prices for a large number of quantities. We subsequently show that the QDF fits very well with 66 discount schedules found in practice. We discuss that the QDF and related indicators can be a useful tool in supplier selection and negotiation processes. It can also be used for competitive analyses, multiple sourcing decisions, and allocating savings for purchasing groups. Additionally, the QDF can be included in research models incorporating quantity discounts. We conclude the paper with an outlook on further QDF research regarding the characterization of commodity markets from a demand elasticity point of view.     

Integrative Cycle Scheduling Approach for a Capacitated Flexible Assembly System*

This study revisits the traditional single stage, multi-item, capacitated lot-sizing problem (CLSP) with a new integrative focus on problem structuring. Unlike past research, we develop integrative cycle scheduling approaches which simultaneously address lot-sizing, capacity, and sequencing issues. Our purposes are to (1) explore the effect of sequencing on inventory levels, (2) examine the problem of infeasibility in the economic lot scheduling problem (ELSP), and (3) provide a simple methodology of generating low-cost cycle schedules in an environment with discrete shipping, dynamic demands, limited capacity, zero setup cost, and sequence-independent setup times. Our procedures are compared to benchmark cycle scheduling approaches in terms of both inventory cost and computation time under different demand scenarios, using the operating data from a flexible assembly system (FAS) at the Ford Motor Company's Sandusky, Ohio plant.     

Scheduling in a Management Context: Uncertain Processing Times and Non-Regular Performance Measures*

Decision makers often face scheduling problems in which processing times are not known with certainty. Non-regular performance measures, in which both earliness and tardiness are penalized, are also becoming more common in both manufacturing and service operations. We model a managerial environment with task processing times (which include sequenceindependent set-up times) prescribed by three-parameter lognormal distributions. Upon completion, each task derives a reward given by a particular piecewise-linear reward function. The objective is to select a sequence of tasks maximizing the expected total reward. The relative generality of the problem renders many enumerative methods inapplicable or computationally intractable. To overcome such difficulties we develop efficient priorityinduced construction (PIC) heuristics which build up a complete schedule by inserting tasks (singly from a list) into a partial sequence of tasks. In each partial and complete sequence a period of idle time is permitted prior to the first task. Performance on realistic-sized problems is very encouraging, with cost penalties averaging less than one percent.     

Multi-Item Grouping Algorithm Yielding Near-Optimal Logistics Cost

This article describes an algorithm used to formulate an inbound consolidation strategy when multi-items are replenished in groups and when total logistics cost is to be minimized. The importance of this algorithm is threefold (1) no optimal procedure exists for grouping multi-items when minimizing total logistics cost, (2) a complete enumeration of all possible groups (from which the optimal grouping set can be identified) is impractical due to the combinatorial nature of the grouping problem, and (3) no other heuristics have been developed that adequately reflect shipping cost in the analysis like this one does. We report the experience of using this algorithm to group and reorder 75 selected ensembles containing a total of 517 inventory items of a retail merchandising firm.     

Efficient Heuristics for MRP Lot Sizing with Variable Production/Purchasing Costs*

Two heuristics based on branch and bound (B&B) are developed to solve closed-loop material requirements planning (MRP) lot-sizing problems that have general product structures and variable costs. A “look ahead method'’(LAM) heuristic allows for variable production/purchasing costs and uses a single-level B&B procedure to rapidly improve lower bound values; thus, LAM efficiently uses computer-storage capacity and allows solution of larger problems. The “total average modification'’(TAM) heuristic uses B&B, applied level by level, and modified setup and carrying costs to solve the variable production/purchasing costs MRP lot-sizing problem. LAM and TAM are tested on problems and compared to heuristics in the literature. TAM may be used to solve large MRP lot-sizing problems encountered in practice.     

IMPLICIT OPTIMAL AND HEURISTIC LABOR STAFFING IN A MULTIOBJECTIVE,MULTILOCATION ENVIRONMENT*

This paper presents a tractable set of integer programming models for the days-off scheduling of a mix of full- and part-time employees working α to β days/week (cycle) in a multiple-objective, multiple-location environment. Previous models were formulated to specifically schedule part-time employees working either two or three days per week. These models were intractable because they required complete employee schedule information. The new models are deemed implicit optimal since they are required to supply only essential information. While the number of variables in previous models is an exponential increasing function of β-α, the size of three of the new models is independent of α and β. The first three models developed here (as in [18]) deal with the trade-offs between idle time, the number of employees required to work at multiple “locations,” and the size of the total labor pool. The inherent flexibility of the implicit modeling approach is illustrated by the presentation of various modifications of the basic models. These modifications permit the use of preference weights on the number of employee work days/week (cycle) or the minimization of payroll costs where differential pay rates exist. These latter models may also be formulated such that idle time is ignored, constrained or minimized. The execution time for the implicit models (on a CDC CYBER 730 computer with commercially available software) averaged well under five seconds on 1200 trial problems for the type of application considered in [18]. A solution was obtained in less than 46 seconds of CPU time for a trial problem which would have required over 1.4 million integer variables with previous models. The availability of optimal solutions was invaluable in the development of two heuristics designed to deal with the trade-offs of [16]. In an experimental analysis a previous heuristic produced results which averaged from 74 to 508 percent above optimum across six experimental conditions. The comparable new heuristic produced results which averaged from 3 to 8 percent above optimum for the same experimental conditions. The paper concludes by developing a framework to integrate the results of this research with the tour scheduling problem and by identifying several other areas for related research.     

A COMPARISON OF SEQUENCING RULES FOR A TWO-STATE HYBRID FLOW SHOP

A common manufacturing environment in many industries (such as the glass, steel, paper, costume jewelry, and textile industries) is a hybrid flow shop. This system has continuous-process machinery in the fist state of manufacturing and repetitive-batch equipment in the second. Little research has investigated this type system. Scheduling managers of hybrid flow shops tend either to use existing job-shop rules or to devise their own rules. These approaches often are less than adequate for efficient scheduling. In this paper we extend the rule presented by Narasimhan and Panwalker [4] to include a general class of hybrid flow shops. This extenstion, called the generalized cumulative minimum-deviation (GCMD) rule, is compared under various operation conditions to three other sequencing rules: shortest processing time, longest processing time, and minimum deviation. The operating conditions are determined by the number of machines at both stages. The results of 7200 simulation runs demonstrate that the GCMD rule is better than the other rules in minimizing each of five chosen criteria. Thus, the GCMD rule can help managers to schedule hybrid flow shops efficiently to achieve various corporate objectives.