bluuebunny/crossref_metadata_2025_split huggingface dataset:
A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths
Authors: McCormick S. Thomas , Smallwood Scott R. , Spieksma Frits C. R. 
Published: December 2003

The following multiprocessor scheduling problem was motivated by scheduling maintenance periods for aircraft. Each maintenance period is a job, and the maintenance facilities are machines. In this context, there are very few different types of maintenances performed, so it is natural to consider the problem with only a small, fixed number C of different types of jobs. Each job type has a processing time, and each machine is available for the same length of time. A machine can handle at most one job at a time, all jobs are released at time zero, there are no due dates or precedence constraints, and preemption is not allowed. The question is whether it is possible to finish all jobs. We call this problem the Multiprocessor Scheduling Problem with C job lengths (MSPC). Scheduling problems such as MSPC where we can partition the jobs into relatively few types such that all jobs of a certain type are identical are often called high-multiplicity problems. High-multiplicity problems are interesting because their input is very compact: The input to MSPC consists of only 2C + 2 numbers. For the case C = 2 we present a polynomial-time algorithm. We show that this algorithm guarantees a schedule that uses the minimum possible number of different one-machine schedules, namely three. Further, we extend this algorithm to the case of machine-dependent deadlines (uniform parallel machines), to a multi-parametric case (that contains the case of unrelated parallel machines), and to some related covering problems. Finally, we give some counterexamples showing why our results do not extend to the case C > 2.
Quitting Games
Authors: Solan Eilon , Vieille Nicolas 
Published: December 2003

Quitting games are n-player sequential games in which, at any stage, each player has the choice between continuing and quitting. The game ends as soon as at least one player chooses to quit; player i then receives a payoff riS, which depends on the set S of players that did choose to quit. If the game never ends, the payoff to each player is 0. The paper has four goals: (i) We prove the existence of a subgame-perfect uniform ε-equilibrium under some assumptions on the payoff structure; (ii) we study the structure of the ε-equilibrium strategies; (iii) we present a new method for dealing with n-player games; and (iv) we study an example of a four-player quitting game where the “simplest” equilibrium is cyclic with Period 2. We also discuss the relation to Dynkin's stopping games and provide a generalization of our result to these games.
First-Order Optimality Conditions for Degenerate Index Sets in Generalized Semi-Infinite Optimization
Authors: Stein Oliver 
Published: December 2003

We present a general framework for the derivation of first-order optimality conditions in generalized semi-infinite programming. Since in our approach no constraint qualifications are assumed for the index set, we can generalize necessary conditions given by Rückmann and Shapiro (1999) as well as the characterizations of local minimizers of order one, which were derived by Stein and Still (2000). Moreover, we obtain a short proof for Theorem 1.1 in Jongen et al. (1998). For the special case when the so-called lower-level problem is convex, we show how the general optimality conditions can be strengthened, thereby giving a generalization of Theorem 4.2 in Rückmann and Stein (2001). Finally, if the directional derivative of a certain optimal value function exists and is subadditive with respect to the direction, we propose a Mangasarian-Fromovitz-type constraint qualification and show that it implies an Abadie-type constraint qualification.
The Symmetric Traveling Salesman Polytope Revisited
Authors: Naddef Denis , Pochet Yves 
Published: December 2003

In this paper we present a tour of the symmetric traveling salesman polytope, focusing on inequalities that can be defined on sets of nodes. Most widely known inequalities are of this type. Many papers have appeared that give increasingly complex valid inequalities for this polytope, but little intuition on why these inequalities are valid has been given. To help in understanding these inequalities, we develop an intuition into their validity by giving a unifying way of defining them through a sequential lifting procedure. This procedure is based on lifting the slack variables associated with subtour elimination inequalities defined on sets of nodes (called teeth). We apply this procedure to some known classes of valid inequalities for the traveling salesman polytope (TSP) respectively comb, brush, star, path, and bipartition inequalities, where the lifting coefficients are sequence independent. For comb, star, and bipartition inequalities, we provide new and noninductive proofs of validity directly inspired by this lifting procedure. We also give an example where a facet-defining inequality is derived from the lifting procedure, but where the lifting coefficients are sequence dependent. We finally study the ladder inequalities and show that they can be generated by an extension of the general procedure, where the lifted variables are different from the slack variables of subtour elimination inequalities.
Risk, Ambiguity, and the Separation of Utility and Beliefs
Authors: Ghirardato Paolo , Marinacci Massimo 
Published: December 2003

We introduce a general model of static choice under uncertainty, arguably the weakest model achieving a separation of cardinal utility and a unique representation of beliefs. Most of the nonexpected utility models existing in the literature are special cases of it. Such separation is motivated by the view that tastes are constant, whereas beliefs change with new information. The model has a simple and natural axiomatization. Elsewhere (forthcoming), we show that it can be very helpful in the characterization of a notion of ambiguity aversion, as separating utility and beliefs allows us to identify and remove aspects of risk attitude from the decision maker's behavior. Here we show that the model allows us to generalize several results on the characterization of risk aversion in betting behavior. These generalizations are of independent interest, as they show that some traditional results for subjective expected utility preferences can be formulated only in terms of binary acts.
A Generalized Stochastic Differential Utility
Authors: Lazrak Ali , Quenez Marie Claire 
Published: December 2003

This paper generalizes, in the setting of Brownian information, the Duffie–Epstein (1992) stochastic differential formulation of intertemporal recursive utility (SDU). We provide a utility functional of state-contingent consumption plans that exhibits a local dependency with respect to the utility intensity process (the integrand of the quadratic variation) and call it the generalized SDU. This mathematical generalization of the SDU permits, in fact, more flexibility in the separation between risk aversion and intertemporal substitution and allows to model asymmetry in risk aversion. We extensively use the backward stochastic differential equation theory to give sufficient conditions for comparative and absolute risk aversion behavior as well as aversion to specific directional risk. Additionally, we discuss whether our functional exhibits monotonicity to its information filtration argument. For purposes of illustration, we provide some applications to the consumption/portfolio strategy selection problem in a complete securities market.
Drift Conditions for Matrix-Analytic Models
Authors: Latouche Guy , Taylor P. G. 
Published: December 2003

In his seminal work, Neuts gave drift criteria by which one can determine whether processes of GI/M/1 or M/G/1 type are positive recurrent. Recently, a different drift condition to determine the ergodic character of a quasi-birth-and-death process (QBD) appeared in the literature, although its justification does not seem to have been formally established. In this paper, we provide a proof for this new drift condition in a general context. We also give a simple proof for Neuts' original condition and establish a number of new drift conditions for the ergodic character of matrix-analytic models.
Management of Worksharing Systems
Authors: McClain John O. , Schultz Kenneth L. , Thomas L. Joseph 
Published: December 2003

Worksharing occurs in serial manufacturing when machines are not uniquely assigned to workers. For example, two workers can operate three machines by alternating usage of the middle one. In some other worksharing systems operators move down the line carrying an item (or batch) with them, working on it at each machine until they are met by another worker who is coming back upstream. The work is then handed off even if the operation is underway. “Bucket Brigade” and “TSS” are worksharing systems based on this idea. This paper examines worksharing in a variety of situations, including unequal work content across machines, uncertain processing times, unequal workers, handoffs with and without preemption, and a range of machine-to-worker ratios. Some systems restrict workers to “zones” of machines. Work zones must overlap if sharing is to occur. The appropriate size of the overlapis shown to depend on the circumstances. Inventory-based rules to control access to shared machines are demonstrated to increase productivity when processing times vary. Worker sequence is found to be quite important; Slowest-to-Fastest is recommended for some situations, but is shown to perform poorly in others. Finally, the issue of whether or not to allow preemption is shown to have a large impact on productivity if inventory is not allowed, and to strongly affect the choice of designs when inventory is allowed. With and without preemption, proper combinations of worker sequence, zone size, and production control rules are shown to nearly eliminate idle time.
A Modeling Framework for Category Assortment Planning
Authors: Chong Juin-Kuan , Ho Teck-Hua , Tang Christopher S. 
Published: December 2003

The complexity of managing a category assortment has grown tremendously in recent years due to the increased product turnover and proliferation rates in most categories. It is an increasingly difficult task for managers to find an effective assortment due to uncertain consumer preferences and the exponential number of possible assortments. This paper presents an empirically based modeling framework for managers to assess the revenue and lost sales implication of alternative category assortments. Coupled with a local improvement heuristic, the modeling framework generates an alternative category assortment with higher revenue.This framework, which consists of a category-purchase-incidence model and a brand-share model, is calibrated and validated using 60,000 shopping trips and purchase records. Specifically, the purchase-incidence model predicts the probability of an individual customer who purchases (and who does not purchase) from a given product category during a shopping trip. The no-purchase probability enables us to estimate lost sales due to assortment changes in the category. The brand-share model predicts which brand the customer chooses if a purchase incidence occurs in the category. Our brand-share model extends the classical Guadagni and Little model (1983) by utilizing three new brand-width measures that quantify the similarities among products of different brands within the same category.We illustrate how our modeling framework is used to reconfigure the category assortment in eight food categories for five stores in our data set. This reconfiguration exercise shows that a reconfigured category assortment can have a profit improvement of up to 25.1% with 32 products replaced. We also demonstrate how our modeling framework can be used to gauge lost sales due to assortment changes. We find the level of lost sales could range from 0.9% to 10.2% for a period of 26 weeks.
Multilocation Combined Pricing and Inventory Control
Authors: Federgruen Awi , Heching Aliza 
Published: December 2003

We consider the problem of managing inventories and dynamically adjusting retailer prices in distribution systems with geographically dispersed retailers. More specifically, we analyze the following single item, periodic review model. The distribution of demand in each period, at a given retailer, depends on the item's price according to a stochastic demand function. These stochastic demand functions may vary by retailer and by period. The replenishment process consists of two phases: In some or all periods, a distribution center may place an order with an outside supplier. This order arrives at the distribution center after an “order leadtime” and is then, in the second phase, allocated to the retailers. Allocations arrive after a second “allocation leadtime.” We develop an approximate model that is tractable and in which an optimal policy of simple structure exists. The approximate model thus provides analytically computable approximations for systemwide profits and other performance measures. Moreover, the approximate model allows us to prove how various components of the optimal strategy (i.e., prices and order-up-to levels) respond to shifts in the model parameters, e.g., to shifts in the retailers' demand functions. In addition, we develop combined pricing, ordering, and allocation strategies and show that the system's performance under these strategies is well gauged by the above approximations. We use this model to assess the impact of different types of geographic dispersion on systems with dynamically varying prices and how different system parameters (e.g., leadtimes, coefficients of variation of individual retailers' demand, price elasticities) contribute to this impact. Similarly, we use the model to gauge the benefits of coordinated replenishments under dynamic pricing, and how these benefits increase as the allocation decisions of the systemwide orders to individual retailers are postponed to a later point in the overall replenishment leadtime. We report on a comprehensive numerical study based on data obtained from a nationwide department store chain.
Newsvendor Networks: Inventory Management and Capacity Investment with Discretionary Activities
Authors: Mieghem Jan A. Van , Rudi Nils 
Published: December 2003

We introduce a class of models, called newsvendor networks, that allow for multiple products and multiple processing and storage points and investigate how their single-period properties extend to dynamic settings. Such models provide a parsimonious framework to study various problems of stochastic capacity investment and inventory management, including assembly, commonality, distribution, flexibility, substitution and transshipment. Newsvendor networks are stochastic models with recourse that are characterized by linear revenue and cost structures and a linear input-output transformation. While capacity and inventory decisions are locked in before uncertainty is resolved, some managerial discretion remains via ex-post input-output activity decisions. Ex-post decisions involve both the choice of activities and their levels and can result in subtle benefits. This discretion in choice is captured through alternate or “nonbasic” activities that can redeploy inputs and resources to best respond to resolved uncertain events. Nonbasic activities are never used in a deterministic environment; their value stems from discretionary flexibility to meet stochastic demand deviations from the operating point. The optimal capacity and inventory decisions balance overages with underages. Continuing the classic newsvendor analogy, the optimal balancing conditions can be interpreted as specifying multiple “critical fractiles” of the multivariate demand distribution; they also suggest appropriate measures for and trade-offs between product service levels. This paper shows that the properties of optimal newsvendor network solutions extend to a dynamic setting under plausible conditions. Indeed, we establish dynamic optimality of inventory and capacity policies for the lost sales case. Depending on the nonbasic activities, this also extends to the backordering case. Analytic- and simulation-based solution techniques and graphical interpretations are presented and illustrated by a comprehensive example that features discretionary input commonality and a flexible processing resource.
Scheduling a Major College Basketball Conference—Revisited
Authors: Henz Martin 
Published: December 2003

Nemhauser and Trick presented the problem of finding a timetable for the 1997/1998 Atlantic Coast Conference (ACC) in basketball. Their solution, found with a combination of integer programming and exhaustive enumeration, was accepted by the ACC. Finite-domain constraint programming is another programming technique that can be used for solving combinatorial search problems such as sports tournament scheduling. This paper presents a solution of round-robin tournament planning based on finite-domain constraint programming. The approach yields a dramatic performance improvement, which makes an integrated interactive software solution feasible.
Online Searching
Authors: Jaillet Patrick , Stafford Matthew 
Published: December 2003

We consider the problem of searching m branches which, with the exception of a common source s, are disjoint (hereafter called concurrent branches). A searcher, starting at s, must find a given “exit” t whose location, unknown to the searcher, is on one of the m branches. The problem is to find a strategy that minimizes the worst-case ratio between the total distance traveled and the length of the shortest path from s to t. Additional information may be available to the searcher before he begins his search. In addition to finding optimal or near optimal deterministic online algorithms for these problems, this paper addresses the “value” of getting additional information before starting the search.
Wavelength Routing and Assignment in a Survivable WDM Mesh Network
Authors: Kennington Jeffery , Olinick Eli , Ortynski Augustyn , Spiride Gheorghe 
Published: December 2003

All-optical networks with wavelength division multiplexing (WDM) capabilities are prime candidates for future wide-area backbone networks. The simplified processing and management of these very high bandwidth networks make them very attractive. A procedure for designing low cost WDM networks is the subject of this investigation. In the literature, this design problem has been referred to as the routing and wavelength assignment problem. Our proposed solution involves a three-step process that results in a low-cost design to satisfy a set of static point-to-point demands. Our strategy simultaneously addresses the problem of routing working traffic, determining backup paths for single node or single link failures, and assigning wavelengths to both working and restoration paths. An integer linear program is presented that formally defines the routing and wavelength assignment problem (RWA) being solved along with a simple heuristic procedure. In an empirical analysis, the heuristic procedure successfully solved realistically sized test cases in under 30 seconds on a Compaq AlphaStation. CPLEX 6.6.0 using default settings required over 1,000 times longer to obtain only slightly better solutions than those obtained by our new heuristic procedure.
Flow Management to Optimize Retail Profits at Theme Parks
Authors: Rajaram Kumar , Ahmadi Reza 
Published: December 2003

In many theme parks, stores are located within major attractions to sell related merchandise. Sales at such stores form a significant portion of theme park profits. Typically, store sales depend upon visitor flows through the attraction, customer satisfaction with the attraction, and the merchandise at the store. In addition, such stores constitute a unique retail environment, as visitor flows to attractions can be managed and stores are not competitors, but belong to the same parent company. This provides the opportunity to increase store sales by interfacing park operations, which manages visitor flows by setting schedules and capacity of attractions, with the store-level merchandising process, which determines which and how much product to order. Motivated by a study at Universal Studios Hollywood (USH), we develop a flow management model to link park operations with store-level merchandising. This model sets the capacities and schedules of the major attractions to increase visitor flows to high-profit retail areas subject to visitor satisfaction, capacity, scheduling, and flow-balance constraints. In addition, this model serves as an important tool to generate and evaluate various strategies aimed at increasing theme park profitability at USH.
Enterprise-Wide Optimization of Total Landed Cost at a Grocery Retailer
Authors: Erhun Feryal , Tayur Sridhar 
Published: December 2003

We describe an enterprise-wide tool for tactical planning at a grocery retailer. The tool enables a “total landed cost” perspective by coordinating decisions across functions of the supply chain. It dynamically optimizes across logistics, purchasing, and warehouse management, while considering the necessary joint replenishment economies and accounting for a wide variety of complexities, such as discounts on total order quantity, intermittent demand, multiple distribution centers, vendor deals and forward buys, and promotions. The application combines appropriate operations research techniques to solve the problem; furthermore, it is created in the newly available information technology infrastructure. The entire application “sits above” and coordinates existing execution tools from commercial vendors by setting key operating targets and providing operational guidance. Within weeks of a pilot, we observed a reduction in on-hand inventories, an increase in service levels, and substantial improvements in logistics decisions. The total landed cost is substantially lower—with an improvement of 20.8% of operating costs, or 11.6% of net profits—while providing superior fulfillment to the stores.
Race-Related Differences in Promotions and Support: Underlying Effects of Human and Social Capital
Authors: James Erika Hayes 
Published: December 2003

This study examined two alternative explanations for disparity in reported work-related experiences and outcomes between black and white managers: treatment discrimination because of race, and differences in human and social capital. Education and training, representing human capital, and racial similarity of network ties and proportion of strong ties, representing social capital, were used to predict whether human and social capital would mediate the relationship between race and the work-related experiences and outcomes under investigation. Results of a survey of black and white managers in a Fortune 500 financial services firm indicate that black managers reported a slower rate of promotion and less psychosocial support than white managers. Race had both a direct and an indirect effect on these outcomes. Participation in company training significantly predicted reported promotion rates, but race remained a significant predictor. Additional analysis revealed that race moderates the relationship between human capital and promotion rate and suggests a type of treatment discrimination against blacks. Contrary to predictions, social capital did not predict promotion rate, although social capital mediated the relationship between race and psychosocial support. Black managers reported having less social capital than whites, and social capital, in turn, was positively related to the receipt of psychosocial support. No differences were found between blacks and whites in their receipt of career-related support.