bluuebunny/crossref_metadata_2025 huggingface dataset:
Scheduling Batches with Sequential Job Processing for Two-Machine Flow and Open Shops
Authors: Glass C.A. , Potts C.N. , Strusevich V.A.
Published: December 2003

In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these as consistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested.
The Online TSP Against Fair Adversaries
Authors: Blom Michiel , Krumke Sven O. , de Paepe Willem E. , Stougie Leen
Published: December 2003

In the online traveling salesman problem, requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman that finishes as early as possible.

Performance of algorithms is measured through their competitive ratio, comparing the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline solution. Objections against such omnipotent adversaries have lead us to devise an adversary that is in a natural way, in the context of routing problems, more restricted in power.

For the exposition we consider the online traveling salesman problem on the metric space given by ℝ0+, the non-negative part of the real line. We show that a very natural strategy is 3/2-competitive against the conventional adversary, which matches the lower-bound on competitive ratios achievable for algorithms for this problem.

Against the more “fair adversary”, that we propose, we show that there exists an algorithm with competitive ratio (1 + √17)/4 ≈ 1.28 and provide a matching lower bound.

We also show competitiveness results for a special class of algorithms (called zealous algorithms) that do not allow waiting time for the server as long as there are requests unserved.
Non-Approximability Results for Scheduling Problems with Minsum Criteria
Authors: Hoogeveen Han , Schuurman Petra , Woeginger Gerhard J.
Published: December 2003

We provide several non-approximability results for deterministic scheduling problems whose objective is to minimize the total job completion time. Unless 𝒫 =𝒩𝒫, none of the problems under consideration can be approximated in polynomial time within arbitrarily good precision. Most of our results are derived by APX-hardness proofs.

We show that, whereas scheduling on unrelated machines with unit weights is polynomially solvable, the problem becomes APX-hard if release dates or weights are added. We further show APX-hardness for scheduling in flow shops, job shops, and open shops. We also investigate the problems of scheduling on parallel machines with precedence constraints and unit processing times, and two variants of the latter problem with unit communication delays; for these problems we provide lower bounds on the worst-case behavior of any polynomial-time approximation algorithm through the gap-reduction technique.
Addendum to "Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method"
Authors: Mészáros Csaba , Gondzio Jacek
Published: December 2003

In this note we point out that the assumptions of Propositions 1 and 2 in Gondzio (1997) are not sufficiently restrictive. We give an example that demonstrates the lack of precision in these propositions and discuss the necessary modifications of the propositions.
A Parallel, Linear Programming-based Heuristic for Large-Scale Set Partitioning Problems
Authors: Linderoth Jeff T. , Lee Eva K. , Savelsbergh Martin W. P.
Published: December 2003

We describe a parallel, linear programming and implication-based heuristic for solving set partitioning problems on distributed memory computer architectures. Our implementation is carefully designed to exploit parallelism to greatest advantage in advanced techniques like preprocessing and probing, primal heuristics, and cut generation. A primaldual subproblem simplex method is used for solving the linear programming relaxation, which breaks the linear programming solution process into natural phases from which we can exploit information to find good solutions on the various processors. Implications from the probing operation are shared among the processors. Combining these techniques allows us to obtain solutions to large and difficult problems in a reasonable amount of computing time.
Sorting Permutations by Reversals Through Branch-and-Price
Authors: Caprara Alberto , Lancia Giuseppe , Ng See-Kiong
Published: December 2003

We describe an exact algorithm for the problem of sorting a permutation by the minimum number of reversals, originating from evolutionary studies in molecular biology. Our approach is based on an integer linear programming formulation of a graph-theoretic relaxation of the problem, calling for a decomposition of the edge set of a bicolored graph into the maximum number of alternating cycles. The formulation has one variable for each alternating cycle, and the associated linear programming relaxation is solved by column generation.

A major advantage with respect to previous approaches is that the subproblem to face in the column-generation phase no longer requires the solution of min-cost general matching problems, but of min-cost bipartite matching problems. Experiments show that there is a tremendous speed-up in going from general matching to bipartite matching, although the best-known algorithms for the two problems have the same theoretical worst-case complexity. We also show the worst-case ratio between the lower bound value obtained by our new method and previous ones.

We illustrate the effectiveness of our approach through extensive computational experiments. In particular, we can solve to proven optimality the largest real-world instances from the literature in a few seconds, and the other (smaller) real-world instances within a few milliseconds on a workstation. Moreover, we can solve to optimality random instances with n + 100 within 3 seconds, and with n + 200 within 15 minutes, where n is the size of the permutation, whereas the size of the instances solvable by previous approaches was at most 100. We also describe a polynomial-time heuristic algorithm that consistently finds solutions within 2% of the optimum for random instances with n up to 1000.
On the Design Problem of Multitechnology Networks
Authors: Chamberland Steven , Sansò Brunilde
Published: December 2003

In this article we propose a model for the topological design problem of multitechnology networks that includes the location of switches and their port configuration, the design of an access network (with single and double access links) and a backbone network. The model specifically takes into account different types of modular switches where each type is characterized by its cost, its capacity in terms of the number of slots, and by its switch fabric capacity. The mutitechnology qualifier stems from the fact that several technologies and rates can be used in the access network. The proposed model is of the integer-programming variety, and in order to find a good solution, we propose a starting heuristic that provides an initial solution and the tabu-search algorithm to improve the solution. Lower bounds are proposed and used to assess the performance of the tabu-based approach. Numerical results for randomly generated problems with up to 500 clients and 50 potential switch sites are presented. The tabu-search algorithm produced solutions that were, on average, within 2.11% of the best lower bound.
An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem
Authors: Congram Richard K. , Potts Chris N. , van de Velde Steef L.
Published: December 2003

This paper introduces a new neighborhood search technique, called dynasearch, that uses dynamic programming to search an exponential size neighborhood in polynomial time. While traditional local search algorithms make a single move at each iteration, dynasearch allows a series of moves to be performed. The aim is for the lookahead capabilities of dynasearch to prevent the search from being attracted to poor local optima. We evaluate dynasearch by applying it to the problem of scheduling jobs on a single machine to minimize the total weighted tardiness of the jobs. Dynasearch is more effective than traditional first-improve or best-improve descent in our computational tests. Furthermore, this superiority is much greater for starting solutions close to previous local minima. Computational results also show that an iterated dynasearch algorithm in which descents are performed a few random moves away from previous local minima is superior to other known local search procedures for the total weighted tardiness scheduling problem.
Assembly-Line Scheduling with Concurrent Operations and Parallel Machines
Authors: Kyparisis George J. , Koulamas Christos
Published: December 2003

This paper addresses the assembly-line scheduling problem with concurrent operations per stage and parallel machines. This problem can be briefly described as the problem of sequencing a predetermined set of parts with known processing-time requirements through anr-station assembly line so that the makespan is minimized. A set of concurrent operations must be performed at each station on each part. This set of operations is usually partdependent since different parts have different processing requirements. In this paper, we construct schedules in quadratic time for this strongly NP-hard problem with an absolute performance guarantee independent of the number of jobs. This makes our schedules asymptotically optimal as the number of jobs becomes very large. The implementation of our schedules facilitates the efficient use of concurrent operations and prevents the assembly line from degenerating into performing operations serially, which would result in low production rates. We utilize compact vector summation techniques and first construct a schedule for the case where each concurrent operation is performed by a single machine. We then generalize our schedule to the case where each concurrent operation is performed by a set of identical parallel machines.
A Linear Programming Approach to Discriminant Analysis with a Reserved-Judgment Region
Authors: Lee Eva K. , Gallagher Richard J. , Patterson David A.
Published: December 2003

A linear-programming model is proposed for deriving discriminant rules that allow allocation of entities to a reserved-judgment region. The size of the reserved-judgment region, which can be controlled by varying parameters within the model, dictates the level of aggressiveness (cautiousness) of allocating (misallocating) entities to groups. Results of simulation experiments for various configurations of normal and contaminated normal three-group populations are reported for a variety of parameter selections. Results of cross-validation experiments using real data sets are also reported. Both the simulation and cross-validation experiments include comparison with other discriminant analysis techniques. The results demonstrate that the proposed model is useful for deriving discriminant rules that reduce the chances of misclassification, while maintaining a reasonable level of correct classification.
A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation
Authors: Holmberg Kaj , Yuan Di
Published: December 2003

The multicommodity network-flow model concerns routing of a number of commodities through a capacitated network at minimal cost. In the basic model, it is assumed that for each commodity, the flow can be routed on any path connecting its origin and its destination. In telecommunication applications, where a commodity represents a communication pair, there are often additional time-delay or reliability requirements on paths that are used for routing. These requirements may vary by communication pair, represented by different priority classes. In this paper, we extend the basic multicommodity network-flow model to include such side constraints on paths. The extended problem is NP-hard with the constrained shortest-path problem as a special case. To solve the extended model, we use a column-generation approach, in which the solution is built up successively by path generation. The side constraints are efficiently handled in the path-generation subproblem. We further discuss various enhancements of this approach. Computational results show that the column-generation approach provides an efficient way for solving the extended model, even for fairly large networks.
Optimal Integer Solutions to Industrial Cutting-Stock Problems: Part 2, Benchmark Results
Authors: Degraeve Zeger , Peeters Marc
Published: December 2003

In this paper we present a state-of-the-art version of the branch-and-price procedure of Degraeve and Schrage (1999) for the exact solution of the cutting-stock problem. The average solution time is reduced by a factor of more than 300. This allows us to solve problems twice as large as the largest problems solved in the literature today. The two most important improvements are (1) a hybrid simplex method/subgradient-optimization procedure to find the LP relaxation, and (2) a branching scheme that first focuses on the residual problem throughout the enumeration tree. In addition, the strength of our algorithm is the integration of different components into one comprehensive procedure. The other components are using heuristics intensively, a pruning rule, and the use of a dominance rule. We validate our methodology with both industrial and generated data sets. The performance of our algorithm is compared extensively with other implementations and various heuristics for the problem. The proposed algorithm is very efficient for solving the bin-packing problem as well. The major implication of our methodology is that we solve industrial sizes of an NP-hard problem practically in a time to solve its LP relaxation.
The Reversal Median Problem
Authors: Caprara Alberto
Published: December 2003

In this paper, we study the Reversal Median Problem (RMP), which arises in computational biology as a basic model for the reconstruction of evolutionary trees. Given q genomes, RMP calls for another genome such that the sum of the reversal distances between this genome and the given ones is minimized. So far, the problem has been considered too complex to derive mathematical models useful for its analysis and solution. We provide a powerful graph-theoretic relaxation of RMP, essentially calling for a perfect matching in a graph that forms the maximum number of cycles jointly with q given perfect matchings. By using this relaxation, we can show the complexity of RMP as well as design effective algorithms for its exact and heuristic solution. We report the solution of a few hundred instances associated with real-world genomes.
Relationship-Based Clustering and Visualization for High-Dimensional Data Mining
Authors: Strehl Alexander , Ghosh Joydeep
Published: December 2003

In several real-life data-mining applications, data reside in very high (1000 or more) dimensional space, where both clustering techniques developed for low-dimensional spaces (k-means, BIRCH, CLARANS, CURE, DBScan, etc.) as well as visualization methods such as parallel coordinates or projective visualizations, are rendered ineffective. This paper proposes a relationship-based approach that alleviates both problems, side-stepping the “curse of-dimensionality” issue by working in a suitable similarity space instead of the original high-dimensional attribute space. This intermediary similarity space can be suitably tailored to satisfy business criteria such as requiring customer clusters to represent comparable amounts of revenue. We apply efficient and scalable graph-partitioning-based clustering techniques in this space. The output from the clustering algorithm is used to re-order the data points so that the resulting permuted similarity matrix can be readily visualized in two dimensions, with clusters showing up as bands. While two-dimensional visualization of a similarity matrix is by itself not novel, its combination with the order-sensitive partitioning of a graph that captures the relevant similarity measure between objects provides three powerful properties: (i) the high-dimensionality of the data does not affect further processing once the similarity space is formed; (ii) it leads to clusters of (approximately) equal importance, and (iii) related clusters show up adjacent to one another, further facilitating the visualization of results. The visualization is very helpful for assessing and improving clustering. For example, actionable recommendations for splitting or merging of clusters can be easily derived, and it also guides the user toward the right number of clusters. Results are presented on a real retail industry dataset of several thousand customers and products, as well as on clustering of web-document collections and of web-log sessions.
Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach
Authors: Nauss Robert M.
Published: December 2003

The classical generalized assignment problem (GAP) may be stated as finding a minimum-cost assignment of tasks to agents such that each task is assigned to exactly one agent and such that each agent's resource capacity is honored. This NP-hard problem has applications that include job scheduling, routing, loading for flexible manufacturing systems, and facility location. Due to the difficulty in solving “hard” GAPs to optimality, most recent papers either describe heuristic methods for generating “good” solutions or, in the case of optimizing methods, computational results are limited to 500 to 1,000 binary variables.

In this paper we describe a special purpose branch-and-bound algorithm that utilizes linear programming cuts, feasible-solution generators, Lagrangean relaxation, and subgradient optimization. We present computational results for solving “hard” problems with up to 3,000 binary variables. An unanticipated benefit of the algorithm is its ability to generate good feasible solutions early in the process whose solution quality generally dominates the solutions generated by two recently published heuristics. Furthermore, the computation time required is often less than the time taken by the heuristics. Thus, we have an optimizing algorithm that can be used quite effectively as a heuristic when proof of optimality is not an absolute requirement.
Guided Local Search for the Three-Dimensional Bin-Packing Problem
Authors: Faroe Oluf , Pisinger David , Zachariasen Martin
Published: December 2003

The three-dimensional bin-packing problem is the problem of orthogonally packing a set of boxes into a minimum number of three-dimensional bins. In this paper we present a heuristic algorithm based on guided local search. Starting with an upper bound on the number of bins obtained by a greedy heuristic, the presented algorithm iteratively decreases the number of bins, each time searching for a feasible packing of the boxes. The process terminates when a given time limit has been reached or the upper bound matches a precomputed lower bound. The algorithm can also be applied to two-dimensional bin-packing problems by having a constant depth for all boxes and bins. Computational experiments are reported for two- and three-dimensional instances with up to 200 boxes, showing that the algorithm on average finds better solutions than do heuristics from the literature.
Combinatorial Auctions: A Survey
Authors: de Vries Sven , Vohra Rakesh V.
Published: December 2003

Many auctions involve the sale of a variety of distinct assets. Examples are airport time slots, delivery routes, network routing, and furniture. Because of complementarities or substitution effects between the different assets, bidders have preferences not just for particular items but for sets of items. For this reason, economic efficiency is enhanced if bidders are allowed to bid on bundles or combinations of different assets. This paper surveys the state of knowledge about the design of combinatorial auctions and presents some new insights. Periodic updates of portions of this survey will be posted to this journal's Online Supplements web page at http://joc.pubs.informs.org/OnlineSupplements.html
Improving Performance and Flexibility at Jeppesen: The World's Leading Aviation-Information Company
Authors: Katok Elena , Tarantino William , Tiedeman Ralph
Published: December 2003

Jeppesen Sanderson, Inc. maintains, manufactures, and distributes flight manuals containing safety information for over 300,000 pilots and 400 airlines worldwide. Its service deteriorated when a growing line of over 100,000 aviation charts overwhelmed its production system. We developed optimization-based decision support tools that improved production planning. Concurrently, we developed a method for evaluating investments in production technology. Our work reduced lateness and improved production processes, which led to a decrease in customer complaints, a reduction in costs of nearly 10 percent, an increase in profit of 24 percent, and the creation of a new OR group. Today, OR-based decision support systems are spreading to all areas of the company.
Optimizing Customer Mail Streams at Fingerhut
Authors: Campbell Deb , Erdahl Randy , Johnson Doug , Bibelnieks Eric , Haydock Michael , Bullock Mark , Crowder Harlan
Published: December 2003

Fingerhut mails up to 120 catalogs per year to each of its 7 million customers. With this dense mail plan and mailing decisions made independently for each catalog, many customers were receiving redundant and unproductive catalogs. To identify and eliminate this excessive operational expense, IBM and Fingerhut together developed an optimization system that selects the most profitable sequence of catalogs, called a mail stream, for each customer. With mail streams, Fingerhut makes better mailing decisions at the customer level, resulting in increased profits. Today, Fingerhut runs this application weekly to find the most profitable mail stream for each customer.
Optimization as an Internet Resource
Authors: Fourer Robert , Goux Jean-Pierre
Published: December 2003

The rise of e-commerce promises particularly great benefits for the practice of large-scale optimization. The World Wide Web already offers information, advice, and remote access to software for solving optimization problems. A variety of client programs are helping to increase the scope and convenience of these tools. More sophisticated application service providers will further disseminate optimization-modeling environments and solvers, making their power and variety readily available to a broader range of customers and applications.
E-Commerce and Operations Research in Airline Planning, Marketing, and Distribution
Authors: Smith Barry C. , Günther Dirk P. , Rao B. Venkateshwara , Ratlife Richard M.
Published: December 2003

Many e-commerce principles were pioneered in the airline industry. These include the first business-to-business electronic information exchange and industrywide electronic marketplace. This environment provided unprecedented opportunity for operations research (OR) modeling. By the mid-1980s airlines used customer shopping data to calibrate traveler-demand-and-choice models, analyzed multichannel product-distribution strategies with simulation, and practiced dynamic pricing through yield management. Airlines continue to derive billions of dollars annually from these and derivative models. The availability of reliable, low-cost communications via the Internet is providing new modeling challenges within the airline industry and is also providing similar opportunities in other industries.
Applications and Opportunities for Operations Research in Internet-Enabled Supply Chains and Electronic Marketplaces
Authors: Sodhi Manmohan S.
Published: December 2003

The Internet is creating opportunities to apply optimization. Firms can use operations research (OR) to improve their supply-chain performance within the enterprise whether their supply chains are being Internet-enabled or not. They can increase benefits by using OR to improve planning and execution in Internet-enabled supply chains with an expanded physical scope that includes vendors and customers and with an expanded functional scope that includes product design, marketing, and customer-relationship management.
Quantitative Analysis for Internet-Enabled Supply Chains
Authors: Keskinocak Pinar , Tayur Shidhar
Published: December 2003

A supply chain, from an operations perspective, has three components: sourcing or procurement, manufacturing and distribution, and inventory disposal. In each component, the Internet is significantly affecting how supply chains are being managed, leading to new challenges while ultimately promising to provide value. The likely future is collaborative supply-chain management that promises to make, for the first time, the dream of virtual integration a reality. Quantitative modeling provides companies decision support as well as insights for better management of supply chains. But there are still a number of challenges that require further OR/MS analysis.
Enhancing Competitiveness of the Customer Loan Center at Promistar Financial Corporation
Authors: Mirchandani Prakash , Hegde G. G. , Wendell Richard E.
Published: December 2003

When a prospective automobile buyer seeks dealer financing, the dealer typically faxes the loan application to a number of banks. The consumer loan center of Promistar Financial Corporation, a medium-sized bank in southwestern Pennsylvania, competes with other banks to finance such loans. Competition is fierce with a bank's response time being an important factor in its “winning” the loan. In order to make more effective staffing decisions, the bank asked us to assess the relationship between response time and staffing levels at the loan center. What started out as a staffing analysis quickly became much more. The process of data collection and model building to address the staffing issue led to a number of important insights and a variety of recommendations that the bank implemented. This has led to significant improvements in the loan center's operations.
Value Analysis and Optimization of Reusable Containers at Canada Post
Authors: Duhaime Rochelle , Riopel Diane , Langevin André
Published: December 2003

We analyzed the use and sharing of a logistics package, a returnable container, often out of stock, between Canada Post and its large mailing customers. Standardizing and sharing logistical packaging should bring members of a supply chain tangible benefits from productivity and efficiency gains. We determined that inventory imbalance between supply locations and demand locations caused the problem. We found that different accounting methods gave very different results in calculating the benefits. We concluded that there is always a benefit for the mailer. For Canada Post to benefit, however, the container must be returned quickly. We used a minimum-cost-flow model to confirm that the company has enough containers to satisfy demand. With better planning and control of the inventory, Canada Post can prevent disequilibrium between supply and demand.
A New Approach to Performance Measurement and Goal Setting
Authors: Andrews Bruce H. , Carpentier John J. , Gowen Tracy L.
Published: December 2003

To support their continuous improvement programs, we developed and implemented a performance-measurement and goal-setting system for the six regional water utility operating companies that are all managed by one holding company. The performance-measurement and goal-setting stages both have two sample-based methodological components: (1) estimation of past and future cumulative distribution functions (c.d.f.s) of the key performance metric for a population of operating companies in the industry, and (2) regression analysis of the same metric for comparing period-to-period changes (both past and projected) in the performance of individual operating companies. This system has allowed the holding company to better evaluate and plan for its own performance in relation to that of its peers and to establish credible, individualized goals for its six regional companies based on estimates of their inherent capability.
Optimization Models for Restructuring BASF North America's Distribution System
Authors: Sery Slava , Presti Vince , Shobrys Donald E.
Published: December 2003

By 1995, annual distribution costs for BASF North America's packaged goods were nearly $100 million. The firm explored trade-offs between customer service and operating costs in a redesign effort using linear-programming-based models. The project team adapted formulations to the extensive available data and used a series of formulations to cope with the scale of the project. A flexible modeling tool aided the team in implementing these formulations. The resulting revised distribution system reduced costs and improved customer service, and the modified distribution network took next-day deliveries from 77 percent to 90 percent. Although the team expected reduction in annual costs of 10 percent, subsequent customer service initiatives reduced the potential savings. In studies following the initial distribution changes the team estimated annual costs savings at six percent, but also identified a one-time nine-percent improvement in cash flow from inventory reductions. BASF also applied the models to operations in Scandinavia, Europe, and the Asia-Pacific area.
A Modern Simulation Course for Business Students
Authors: Hwarng H. Brian
Published: December 2003

Simulation was often neglected in undergraduate business curricula for two reasons: (1) simulation was traditionally taught and used in engineering disciplines, and (2) business students lacked training in computer programming and quantitative skills. Powerful microcomputers and user-friendly simulation software have brought about new prospects for simulation modeling. To meet the needs of the modern business world, business schools should widely teach simulation modeling and analysis. I developed an intermediate simulation course at the National University of Singapore for upper-level-undergraduate or graduate business students. Early in the course, migrating from general-purpose spreadsheet modeling to special-purpose simulation modeling is a key step. Modeling real-world problems through team projects is the climax of the course. My rigorous and practical approach proves that students with no simulation or computer-programming background can handle even an intermediate course.
Identifying the NCAA Tournament “Dance Card”
Authors: Coleman B. Jay , Lynch Allen K.
Published: December 2003

The NCAA Basketball Tournament selection committee annually selects the Division I men's teams that should receive at-large bids to the national championship tournament. Although its deliberations are shrouded in secrecy, the committee is supposed to consider a litany of team-performance statistics, many of which outsiders can reasonably estimate. Using a probit analysis on objective team data from 1994 through 1999, we developed an equation that accurately classified nearly 90 percent of 249 “bubble” teams during that time frame and over 85 percent for the 2000 tournament. Given the NCAA Tournament's nickname of the big dance, the equation is effectively the “dance card” that determined whether a team got an invitation from past committees and is also a tool that could aid decision making for future committees. The accuracy of the dance card, and the factors and weights included in it, suggest that the committee is fairly predictable in its decisions, despite barbs from fans, teams, and the media.
Improving Car Body Production at PSA Peugeot Citroën
Authors: Patchong Alain , Lemoine Thierry , Kern Gilles
Published: December 2003

In 1998, following a change in top management, the new CEO of PSA Peugeot Citroën decided to adopt a triple-axis strategy of growth, innovation, and profitability and set an ambitious target for each. To meet these objectives, PSA decided to focus on the car-body shops, which were the bottlenecks of its plants. An R&D team conducted a project to support car-body production for PSA Peugeot Citroën. PSA manufactures over 75 percent of its cars on lines designed and continually improved with the team's new analytic operations research tools. These OR tools, which combine simulation and Markov-chain models of series-parallel systems, have improved throughput with minimal capital investment and no compromise in quality—contributing US $130 million to the bottom line in 2001 alone. The impact of this project went beyond the boundaries of PSA as its suppliers acquired the tools without being requested to do so.
A New Era for Crew Recovery at Continental Airlines
Authors: Yu Gang , Argüello Michael , Song Gao , McCowan Sandra M. , White Anna
Published: December 2003

Airlines face schedule disruptions daily because of unexpected events, including inclement weather, aircraft mechanical problems, and crew unavailability. These disruptions can cause flight delays and cancellations. As a result, crews may not be in position to service their remaining scheduled flights. Airlines must reassign crews quickly to cover open flights and to return them to their original schedules in a cost-effective manner while honoring all government regulations, contractual obligations, and quality-of-life requirements. CALEB Technologies developed the CrewSolver decision-support system for Continental Airlines to generate globally optimal, or near optimal, crew-recovery solutions. Since its implementation, the system has dealt successfully with several high-profile events, including the December 2000 and March 2001 Nor'easter snowstorms, the June 2001 Houston flood, and most dramatically, the September 11th terrorist attacks. In each case, Continental recovered quickly and obtained overall benefits worth millions of dollars. Continental estimates that in 2001 the CrewSolver system helped it save approximately US $40 million for major disruptions only.
Optimizing Periodic Maintenance Operations for Schindler Elevator Corporation
Authors: Blakeley Fred , Argüello Burçin , Cao Buyang , Hall Wolfgang , Knolmajer Joseph
Published: December 2003

Schindler, the world's largest escalator company and second-largest elevator company, maintains tens of thousands of elevators and escalators throughout North America. Thousands of technicians are on the road each day to maintain, repair, and help in emergencies. Each technician's route requires precise and optimized planning. Schindler Elevator Corporation turned to Environmental Systems Research Institute (ESRI) to develop an automated route-scheduling and planning system. ESRI provided a geographic-information-system-integrated application that employs operations research techniques to optimize preventive maintenance operations. It relies on a series of algorithms to assign maintenance work to technicians and to create efficient day-routes by solving the periodic-vehicle-routing problem. These automated tools allow Schindler to restructure and streamline service areas. The optimization system saves over $1 million annually and increases Schindler's managers' awareness of operating revenue.
Managing the Seed-Corn Supply Chain at Syngenta
Authors: Jones Philip C. , Kegler Greg , Lowe Timothy J. , Traub Rodney D.
Published: December 2003

Each year, Syngenta Seeds, Inc. produces over 50 seed-corn hybrids and the following year markets over 100 hybrids under the NK brand name. The fact that growing seed corn is a biological process dependent upon local weather and insect conditions during the growing season complicates production planning. In addition, customers' experiences with a particular hybrid during a given year strongly influence demand for that hybrid during the next year. To help mitigate some of these yield and demand uncertainties, Syngenta (and other seed companies as well) take advantage of a second growing season for seed corn in South America, which occurs after many of the yield uncertainties and some of the demand uncertainties have been resolved or reduced. To better manage this production-planning process, Syngenta and the University of Iowa developed and implemented a second-chance production-planning model. A trial of the model showed that using it to plan 2000 production would have increased margins by approximately $5 million. Today, Syngenta uses this model to plan production for those varieties that account for 80 percent of total sales volume.
Book Reviews
Authors: Lev Benjamin
Published: December 2003

The range of books reviewed is wide, covering theory and applications in operations research, statistics, management science, econometrics, mathematics, computers, and information systems (no software is reviewed). In addition, we include books in other fields that emphasize technical applications. Publishers who wish to have their books reviewed should send them to Professor Benjamin Lev. We list the books received; not all books received can be reviewed because space is limited. Those who would like to review books are urged to send me their names, addresses, and specific areas of expertise. We commission all reviews and do not accept unsolicited book reviews. Readers are encouraged to suggest books that might be reviewed or to ask publishers to send me copies of such books.

The authors or editors of the books reviewed in this issue are Jacek Blazewicz, Klaus H. Ecker, Erwin Pesch, Guenter Schmidt, Jan Weglarz, Eric V. Denardo, Zbigniew Michalewicz, David B. Fogel, Tan Miller, Christoph Schneeweiss, Dileep R. Sule, Stanislav Uryasev, and Panos M. Pardalos.
Decision Support for Allocating Scarce Drugs
Authors: Swaminathan Jayashankar M.
Published: December 2003

The 1998 settlement of a lawsuit by the state of California required 19 pharmaceutical firms to provide $150 million worth of drugs free of charge to more than 150 California clinics and hospitals over a three-year period. We developed a decision-support system that utilizes a multiobjective optimization model and a heuristic solution taking into account the efficiency, effectiveness, and equity of the drug-allocation process. As of November 2002, 90 percent of the total budget has been distributed to the various clinics with the help of this decision-support system.
Teaching OR/MS to MBAs at Warwick Business School: A Turnaround Story
Authors: Robinson Stewart , Meadows Maureen , Mingers John , O'Brien Frances A. , Shale Estelle A. , Stray Stephanie
Published: December 2003

OR/MS is under pressure in MBA programs in the United Kingdom as it is in the United States. To ensure its continuance, members of the operational research group at Warwick Business School redesigned the core OR/MS module. The first attempt at a redesign was a failure. As a result, the module was redesigned again. The second version was a success. Through this process, we have learned many lessons about teaching OR/MS to MBA students, among them the need to have a guiding philosophy, adopt a critical-consumer approach, stress managerial relevance, discuss the context and process of modeling as well as content, and use spreadsheets for analytical work.
High Tech for a Higher Authority: The Placement of Graduating Rabbis from Hebrew Union College—Jewish Institute of Religion
Authors: Bodin Lawrence , Panken Aaron
Published: December 2003

We describe the new placement process used to match the graduating rabbis from Hebrew Union College—Jewish Institute of Religion (HUC-JIR) with congregations. The students involved in this new placement process are scheduled to be ordained as rabbis from HUC-JIR in May, about one month after the placement process is completed, and most students begin their pulpit assignments in July. Embedded in the new placement process are the double-blind match procedure and the double-blind match procedure for couples. These procedures, which we adapted from the procedure used to assign medical school graduates to internships, have been used successfully for placing the graduating rabbinical students at HUC-JIR since 1997.
Scheduling Appointments at Trade Events for the Australian Tourist Commission
Authors: Ernst A. T. , Mills R. G. J. , Welgama P.
Published: December 2003

Many trade events include appointments between buyers and sellers. Each buyer indicates preferences for meetings with various sellers and vice versa. We developed an assignment model and implemented it in the SATE (scheduling appointments at trade events) software. SATE maximizes an objective that weights the preferences of buyers and sellers. Our assignment method schedules more meetings with higher preferences in less computational time than the previous method used. SATE allows organizers of trade events to control appointment scheduling and investigate various scenarios prior to publishing appointment schedules.
Using Technology to Support Pedagogy in an OR/MS Course
Authors: Seal Kala Chand , Przasnyski Zbigniew H.
Published: December 2003

We tried several methods to improve pedagogy in a graduate introductory OR/MS course. We developed digital video instruction modules, animations, computer-based tutorials, and a course Web site and used Web-based feedback, virtual classrooms, and collaborative learning methods to support students' learning. We learned that the course Web site, Web-based feedback, virtual classrooms, and some collaborative learning methods are easy to develop and implement and provide immediate returns. Others, such as digital video instructions, animations, and real-time collaborative computing, need more time but may provide better pedagogic benefits in the long run. The benefits from all the efforts accumulate over time. Individual instructors will have to decide whether the potential benefits provide enough payback, depending upon the reward structure of their institutions.
Sensitivity Analysis and Uncertainty in Linear Programming
Authors: Higle Julia L. , Wallace Stein W.
Published: December 2003

Linear programming (LP) is one of the great successes to emerge from operations research and management science. It is well developed and widely used. LP problems in practice are often based on numerical data that represent rough approximations of quantities that are inherently difficult to estimate. Because of this, most LP-based studies include a postoptimality investigation of how a change in the data changes the solution. Researchers routinely undertake this type of sensitivity analysis (SA), and most commercial packages for solving linear programs include the results of such an analysis as part of the standard output report. SA has shortcomings that run contrary to conventional wisdom. Alternate models address these shortcomings.
Woodward Aircraft Engine Systems Sets Work-in-Process Levels for High-Variety, Low-Volume Products
Authors: Srinivasan Mandyam M. , Ebbing Steven J. , Swearingen Alan T.
Published: December 2003

We developed a method for setting the work-in-process (WIP) levels for products manufactured in a plant that operates in a high-variety, low-volume environment. We implemented the method on a spreadsheet using Visual Basic macros and used an iterative algorithm to find the WIP levels needed to meet required throughputs for different products. We applied the method at Woodward Aircraft Engine Systems, Rockford, Illinois, which produces high-precision components with long setup times. Using the spreadsheet, plant supervisors can quickly analyze several alternate scenarios. They have reduced WIP levels in some cells to one third of their original values.
Optimizing On-Demand Aircraft Schedules for Fractional Aircraft Operators
Authors: Martin Chris , Jones David , Keskinocak Pinar
Published: December 2003

Fractional aircraft ownership programs have revolutionized corporate aviation. For a fraction of the cost, they offer owners the comfort and convenience of a full-time flight department. However, fractional management companies (FMCs) have costly business requirements that neither commercial airlines nor charter airlines face. Two challenges that affect their profitability are (1) the management company, instead of the customer, pays all positioning costs, and (2) FMCs give owners short call-out windows, sometimes as little as four hours before departure and guarantee lift to satisfy their demands. FMCs must operate their fleets efficiently. Bitwise Solutions developed a flexible, integrated decision-support system to help FMCs optimize their fleet schedules and succeed. The system, called FlightOps, handles all aspects of fractional fleet management: reservations, scheduling, dispatch, aircraft maintenance, and crew requirements. It also keeps track of the FAA regulatory requirements for crew duty. The system includes the ScheduleMiser, a CPLEX-based decision-support tool. ScheduleMiser creates an optimal schedule for a fleet of aircraft and a set of owner demands (missions) by minimizing costs while meeting FAA regulations and FMC business rules for feasibility. The mixed-integer model behind ScheduleMiser allows FMCs to manually schedule many types of restrictions on an aircraft's schedule, including maintenance periods, flight restrictions, and manual mission assignments. If an aircraft is not available to fly a mission, the FMC can schedule a comparable or larger available aircraft within its fleet, or it can subcontract a charter aircraft. In November 2000, Raytheon Travel Air, the second largest FMC, started using FlightOps. In a press release, it stated FlightOps helped it produce record numbers in hours flown and aircraft availability over Thanksgiving week 2000. It reported an 18.7 percent reduction in positioning legs for some aircraft and a $4.4 million savings in the first year after implementing our system.
Managing Credit Lines and Prices for Bank One Credit Cards
Authors: Trench Margaret S. , Pederson Shane P. , Lau Edward T. , Ma Lizhi , Wang Hui , Nair Suresh K.
Published: December 2003

We developed a method for managing the characteristics of a bank's card holder portfolio in an optimal manner. The annual percentage rate (APR) and credit line of an account influence card use and bank profitability. Consumers find low APRs and high credit lines attractive. However, low APRs may reduce bank profitability, while indiscriminate increases in credit lines increase the bank's exposure to credit loss. We designed the PORTICO (portfolio control and optimization) system using Markov decision processes (MDP) to select price points and credit lines for each card holder that maximize net present value (NPV) for the portfolio. PORTICO uses account-level historical information on purchases, payments, profitability, and delinquency risk to determine pricing and credit-line changes. In competitive benchmark tests over more than a year, the PORTICO model outperforms the bank's current method and may increase annual profits by over $75 million.