Moshe Dror

Interests

Research

Applied Game Theory; Applied Combinatorial Optimization; Scheduling & Applied Logistics.

Courses

Scholarly Contributions

Books

• Dror, M., & Zeng, S. (2016). FORMULATING PRINCIPAL-AGENT SERVICE CONTRACTS FOR A REVENUE GENERATING UNIT.

Journals/Publications

• Dror, M., Kendall, G., & Rapoport, A. (2016). Elicitation of Strategies in Four Variants of a Round-Robin Tournament: The Case of Goofspiel. IEEE Transactions on Computational Intelligence & AI in Games 8, 209-217.
• Carl, K., & Dror, M. (2015). Multi-Day Bicycle Tour Route Generation. J. of Quantitative Analysis in Sports.
• Zeng, S., & Dror, M. (2015). Formulating Principal-Agent Service Contracts for a Revenue Generating Unit. SpringerBriefs in Operations Management.
• Dror, M., Granot, D., & Yaeger-Dror, M. (2014). Teaching & Learning Guide for: Speech Variation, Utility, and Game Theory. Language and Linguistics Compass, 8/6, 230-242.
• Summerfield, N., & Cohen, M. (2015). City Streets Parking Enforcement Inspection Decisions: The Chinese Postman’s Perspective. European J. of Operational Research, 242, 149-160.
• Carl, K., Brown, S. A., Dror, M., & Durcikova, A. (2013). Bicycle tours: Modeling the perceived exertion of a daily path. Journal of Quantitative Analysis in Sports, 9(2), 203-216.
  More info

  Abstract: The desire to promote healthier and more environmentally conscious methods of commuting has generated increased interest in professional and recreational bicycling in recent years. One of the most important factors cyclists consider when riding is the amount of exertion they will perceive on a given path. In this paper, we build and test a model of the perceived exertion of different categories of cyclists on a daily path within a long bicycle tour. We first propose an additive formula for calculating the perceived exertion of cyclists on component parts of a tour and then present the results of a survey designed to verify the accuracy of the model. Distance, elevation gain, average percent grade, maximum percent grade, and cyclists ' level of expertise are shown to be significant predictors of perceived exertion (p 0.005). Repeated measures analysis indicated that 109 of the 120 perceived exertion levels produced by our model fit the reported perceived exertion levels of the 242 avid cyclists who participated in the validation survey.
• Dror, M., & Kendall, G. (2013). Repeated goofspiel: A game of pure strategy. IEEE Transactions on Computational Intelligence and AI in Games, 5(4), 312-324.
  More info

  Abstract: In this paper, we examine a pure strategy game known as Goofspiel and report on the results of round-robin competitions between 14 programs designed to play this game. Goofspiel is a two-person card game that is easy to play. However, playing this game successfully has proven to be a difficult task. There is no known 'good' strategy for Goofspiel. This is the first time that playing Goofspiel has been examined in a context of a round-robin competition between programs. None of the participating programs won consistently against its rivals. Thus, no clear dominating strategy of play has emerged. In this respect, Goofspiel is similar to the Prisoner's Dilemma where Tit-for-Tat has proven to be a good strategy against many but not against all. This paper introduces Repeated Goofspiel and presents preliminary experimental results. We hope it will motivate further research into this fascinating game. © 2013 IEEE.
• Dror, M., Granot, D., & Yaeger-Dror, M. (2013). Speech variation, utility, and game theory. Linguistics and Language Compass, 7(11), 561-579.
  More info

  Abstract: We review a new perspective for analyzing linguistic variation, diffusion, and change, by introducing into this 'arena' the economists' perception of strategic individual interactions. We invoke basic game theory principles to explain linguistic outcomes of individual speech production in a variety of interactional social settings. We present real-life examples that illustrate our game perspective regarding linguistic interactions and present a number of mappings into well-known game constructs such as the Prisoners' Dilemma, iterated dominance, and extensive form games. Our purpose is to suggest a game theory 'prism' as a plausible methodology for analysis of individual interactional linguistic situations. © 2013 The Author Language and Linguistics Compass © 2013 John Wiley & Sons Ltd.
• Grimes, M., & Dror, M. (2013). Observations on strategies for Goofspiel. IEEE Conference on Computatonal Intelligence and Games, CIG.
  More info

  Abstract: Goofspiel is a zero-sum two player card game in which all information is known by both players. Many strategies exist that leverage random, deterministic, and learning approaches to play, however, no strategy dominates all others. It has been suggested that a hybrid strategy combining two or more of these approaches may provide better results than any of these alone. In this note, we review the strengths and weaknesses of each traditional strategy and make a cursory evaluation of a hybrid 'Good' strategy. © 2013 IEEE.
• Summerfield, N. S., & Dror, M. (2013). Biform game: Reflection as a stochastic programming problem. International Journal of Production Economics, 142(1), 124-129.
  More info

  Abstract: In this paper we examine the biform games modeling framework. More specifically, we recast biform games as two-stage stochastic programming with recourse. The two-stage stochastic programming view of biform games is demonstrated in this paper on an example from Brandenburger and Stuart (2007) regarding a coordination game. We claim that our stochastic programming format for biform games allows for a well established mathematical methodology to enrich the modeling options when applied to biform competitive and cooperative game options.
• Berger, L., Dror, M., & Lynch, J. (2012). Universal number partition problem with divisibility. Discrete Mathematics, 312(10), 1692-1698.
  More info

  Abstract: We examine a version of the Universal Number Partition Problem with a divisibility property referred to as the Universal Shelf Packing Problem (USPP). We show that if a shelf length is a product of powers of two primes the USPP is always partitionable. In the case where the shelf length is a product of three distinct primes we propose an efficient scheme to determine when such a case is not partitionable. We also show that a shelf length that is a product of powers of four or more primes always has at least one partition failure. Our analysis uses elementary number theory, known results related to the linear Diophantine Frobenius problem, and a new result on Frobenius gaps. © 2012 Elsevier B.V. All rights reserved.
• Burer, S., & Dror, M. (2012). Newsvendor games: Convex optimization of centralized inventory operations. TOP, 20(3), 707-728.
  More info

  Abstract: A finite set of outlets with randomly fluctuating demands bands together to reduce costs by buying, storing and distributing their inventory jointly. This is termed inventory centralization and is a type of risk pooling. The expected centralization cost can be lowered even further, without disrupting the demand behavior at individual outlets, by inducing the outlets to correlate their individual demands. Given that the outlets' demands are normally distributed, the lowering of the centralized cost corresponds to a semidefinite optimization problem. This paper establishes a closed-form optimal solution of the semidefinite program and a fair allocation of the centralized cost at optimality. © 2010 Sociedad de Estadística e Investigación Operativa.
• Dror, M., Hartman, B. C., & Chang, W. (2012). The cost allocation issue in joint replenishment. International Journal of Production Economics, 135(1), 242-254.
  More info

  Abstract: Joint replenishment for several products to achieve a lower inventory logistics cost has been a topic of extensive studies. Less attention has been paid to the issue of deciding how the joint replenishment costs should be allocated across the individual products. Ideally, when items are ordered together one would require a stable cost allocation, such that no subset of products subsidizes another subset. When part of each products ordering cost is product specific and part can be shared with other products (like in a 3PL setting of Anily and Haviv), it has been shown that even when a stable allocation exists, such an allocation might be difficult to compute. In addition, usually the components of ordering costs are partially determined using estimates and accounting discretion. This paper provides two main insights for determining an appropriate cost allocation. It provides the means to test how sensitive a stable cost allocation is to a range of cost parameter values. Then, in a computational study, it is shown how to obtain a stable cost allocation without excessive computation. © 2010 Elsevier B.V. All rights reserved.
• Summerfield, N. S., & Dror, M. (2012). Stochastic programming for decentralized newsvendor with transshipment. International Journal of Production Economics, 137(2), 292-303.
  More info

  Abstract: This paper discusses a family of two-stage decentralized inventory problems using a unifying framework (taxonomy) depicted as a multilevel graph. This framework allows us to model and link different problems of competing retailers who independently procure inventory in response to uncertain demand and anticipated inventory decisions of other retailers. In this family of problems, in the ex-post stage, the retailers exercise recourse actions in response to the realized demand and competitors chosen procurement levels. For example, retailers could coordinate inventory transshipment to satisfy shortage with overage based on profit sharing agreements. Our framework provides a unifying parsimonious view using a single methodological prism for a variety of problems. Equally importantly, as recourse options are laid out, our framework clarifies and contributes a modeling connection between problems in a clear taxonomy of models. This unifying perspective explicitly links work that appeared in isolation and offers future research directions. © 2012 Elsevier B.V. All rights reserved.
• Dror, M., & Hartman, B. C. (2011). Survey of cooperative inventory games and extensions. Journal of the Operational Research Society, 62(4), 565-580.
  More info

  Abstract: We examine cooperative games in supply-chain management termed Inventory Games. Supply-chain management has non-cooperative and cooperative interactions between the participating players. We provide a concise survey of cooperative inventory games in the form of extensions on two basic problems. For deterministic games, Economic Order Quantity-like policies with joint replenishment are of primary interest. For stochastic games we examine Newsvendor-like centralization games and their extensions. We conclude with a short summary of a dynamic Newsvendor realization game and directions for further research. © 2011 Operational Research Society Ltd. All rights reserved.
• Suakkaphong, N., & Dror, M. (2011). Managing decentralized inventory and transshipment. TOP, 19(2), 480-506.
  More info

  Abstract: Any decentralized retail or wholesale system of competing entities requires a benefit sharing arrangement when competing entities collaborate after their demands are realized. For instance, consider a distribution system similar to the observed behavior of independent car dealerships. If a dealership does not have in stock the car requested by a customer, it might consider acquiring it from a competing dealer. Such behavior raises questions about procurement strategies that achieve system optimal (first-best) outcomes. In this paper, we examine the existence and uniqueness of pure strategy Nash equilibrium (PSNE) for a decentralized system that adopts a transfer payment approach proposed by Anupindi et al. (Manuf. Serv. Oper. Manag. 4(3):349-368, 2001). In particular, we state a set of conditions on cost parameters and distributions that guarantee uniqueness of PSNE and discuss its consequences. We also examine a situation with incomplete information and expand the scope of the earlier models by relaxing the assumption of satisfying local demand first. That is, we allow the retailers to transship their inventory regardless of the local demand status if such transshipment increases retailer's profit, and observe that this model extension does not affect our results relative to the more restrictive case. In short, our results provide important insights, clarifications, and strategic limitations regarding collaborations in decentralized distribution system. © 2010 Sociedad de Estadística e Investigación Operativa.
• Dror, M., & Sošić, G. (2010). Welcome to the behavioral and quantitative game theory: Conference on future directions. Behavioral and Quantitative Game Theory: Conference on Future Directions 2010, BQGT 2010, 2-4.
• Dror, M., & Steiner, G. (2010). 'Strong''weak' precedence in scheduling: Extensions to seriesparallel orders. Discrete Applied Mathematics, 158(16), 1767-1776.
  More info

  Abstract: We examine computational complexity implications for scheduling problems with job precedence relations with respect to strong precedence versus weak precedence. We propose a consistent definition of strong precedence for chains, trees, and seriesparallel orders. Using modular decomposition for partially ordered sets (posets), we restate and extend past complexity results for chains and trees as summarized in Dror (1997) [5]. Moreover, for seriesparallel posets we establish new computational complexity results for strong precedence constraints for single- and multi-machine problems. © 2010 Elsevier B.V. All rights reserved.
• Burke, E. K., Dror, M., & Orlin, J. B. (2008). Scheduling malleable tasks with interdependent processing rates: Comments and observations. Discrete Applied Mathematics, 156(5), 620-626.
  More info

  Abstract: In this short paper, we examine the problem of scheduling malleable tasks on parallel processors. One of the main aims of the paper is to present a simple complexity interpretation for a number of results for cases with convex and concave processing speed functions. The contribution of this paper is a new unified view of results described in several recent papers. We briefly discuss the implications of our observations on this important family of scheduling problems. © 2007 Elsevier B.V. All rights reserved.
• Dror, M., Guardiola, L. A., Meca, A., & Puerto, J. (2008). Dynamic realization games in newsvendor inventory centralization. International Journal of Game Theory, 37(1), 139-153.
  More info

  Abstract: Consider a set N of n (> 1) stores with single-item and single-period nondeterministic demands like in a classic newsvendor setting with holding and penalty costs only. Assume a risk-pooling single-warehouse centralized inventory ordering option. Allocation of costs in the centralized inventory ordering corresponds to modelling it as a cooperative cost game whose players are the stores. It has been shown that when holding and penalty costs are identical for all subsets of stores, the game based on optimal expected costs has a non empty core (Hartman et al. 2000, Games Econ Behav 31:26-49; Muller et al. 2002, Games Econ Behav 38:118-126). In this paper we examine a related inventory centralization game based on demand realizations that has, in general, an empty core even with identical penalty and holding costs (Hartman and Dror 2005, IIE Trans Scheduling Logistics 37:93-107). We propose a repeated cost allocation scheme for dynamic realization games based on allocation processes introduced by Lehrer (2002a, Int J Game Theor 31:341-351). We prove that the cost subsequences of the dynamic realization game process, based on Lehrer's rules, converge almost surely to either a least square value or the core of the expected game. We extend the above results to more general dynamic cost games and relax the independence hypothesis of the sequence of players' demands at different stages. © 2007 Springer-Verlag.
• Abdullah, S., Ahmadi, S., Burke, E. K., & Dror, M. (2007). Investigating Ahuja-Orlin's large neighbourhood search approach for examination timetabling. OR Spectrum, 29(2), 351-372.
  More info

  Abstract: Since the 1960s, automated approaches to examination timetabling have been explored and a wide variety of approaches have been investigated and developed. In this paper we build upon a recently presented, sequential solution improvement technique which searches efficiently over a very large set of "adjacent" (neighbourhood) solutions. This solution search methodology, originally developed by Ahuja and Orlin, has been applied successfully in the past to a number of difficult combinatorial optimisation problems. It is based on an improvement graph representation of solution adjacency and identifies improvement moves by finding cycle exchange operations using a modified shortest path label-correcting algorithm. We have drawn upon Ahuja-Orlin's basic methodology to develop an effective automated exam timetabling technique. We have evaluated our approach against the latest methodologies in the literature on standard benchmark problems. We demonstrate that our approach produces some of the best known results on these problems. © 2006 Springer.
• Abdullah, S., Ahmadi, S., Burke, E. K., Dror, M., & McCollum, B. (2007). A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem. Journal of the Operational Research Society, 58(11), 1494-1502.
  More info

  Abstract: Neighbourhood search algorithms are often the most effective known approaches for solving partitioning problems. In this paper, we consider the capacitated examination timetabling problem as a partitioning problem and present an examination timetabling methodology that is based upon the large neighbourhood search algorithm that was originally developed by Ahuja and Orlin. It is based on searching a very large neighbourhood of solutions using graph theoretical algorithms implemented on a so-called improvement graph. In this paper, we present a tabu-based large neighbourhood search, in which the improvement moves are kept in a tabu list for a certain number of iterations. We have drawn upon Ahuja-Orlin's methodology incorporated with tabu lists and have developed an effective examination timetabling solution scheme which we evaluated on capacitated problem benchmark data sets from the literature. The capacitated problem includes the consideration of room capacities and, as such, represents an issue that is of particular importance in real-world situations. We compare our approach against other methodologies that have appeared in the literature over recent years. Our computational experiments indicate that the approach we describe produces the best known results on a number of these benchmark problems. © 2007 Operational Research Society Ltd. All rights reserved.
• Bompadre, A., Dror, M., & Orlin, J. B. (2007). Probabilistic analysis of unit-demand vehicle routeing problems. Journal of Applied Probability, 44(1), 259-278.
  More info

  Abstract: We analyze the unit-demand Euclidean vehicle routeing problem, where n customers are modeled as independent, identically distributed uniform points and have unit demand. We show new lower bounds on the optimal cost for the metric vehicle routeing problem and analyze them in this setting. We prove that there exists a constant ĉ > 0 such that the iterated tour partitioning heuristic given by Haimovich and Rinnooy Kan (1985) is a (2 - ĉ)-approximation algorithm with probability arbitrarily close to 1 as the number of customers goes to ∞. It has been a longstanding open problem as to whether one can improve upon the factor of 2 given by Haimovich and Rinnooy Kan. We also generalize this, and previous results, to the multidepot case. © Applied Probability Trust 2007.
• Dror, M., & Hartman, B. C. (2007). Shipment consolidation: Who pays for it and how much?. Management Science, 53(1), 78-87.
  More info

  Abstract: This paper examines the subject of cost allocation in a multiple product inventory system, allowing for consolidation of shipments. If we order multiple items using an economic order quantity (EOQ) policy, and consolidate shipments, part of the ordering cost is shared, and part is specific to each item; we want to find the consolidation choice with optimal total cost and divide the cost fairly among the individual items. Such a fair division is central to a costing system in which no group of items subsidizes the others; there are no free riders! We use a cooperative inventory game to determine when this can be done. This game is usually not concave, so we want to know what consolidation combinations determine when this cost can be fairly divided, using the core of the game. We prove that consolidation of all the items is cheaper exactly if there are fair cost allocations (core of the game is not empty), which happens when the portion of the ordering cost common to all items is not too small. We further show how sensitive the nonempty core result is to adjustments in the cost parameters and show how to determine a threshold value for the shared ordering cost, which assures the existence of a fair cost allocation. © 2007 INFORMS.
• Dror, M., & Orlin, J. B. (2007). Combinatorial optimization with explicit delineation of the ground set by a collection of subsets. SIAM Journal on Discrete Mathematics, 21(4), 1019-1034.
  More info

  Abstract: We examine a selective list of combinatorial optimization problems in NP with respect to inapproximability (Arora and Lund (1997)) given that the ground set of elements N has additional characteristics. For each problem in this paper, the set N is expressed explicitly by subsets of N either as a partition or in the form of a cover. The problems examined are generalizations of well-known classical graph problems and include the minimal spanning tree problem, a number of elementary machine scheduling problems, the bin-packing problem, and the travelling salesman problem (TSP). We conclude that for all these generalized problems the existence of a polynomial time approximation scheme (PTAS) is impossible unless P=NP. This suggests a partial characterization for a family of inapproximable problems. For the generalized Euclidean TSP we prove inapproximability even if the subsets are of cardinality 2. © 2008 Society for Industrial and Applied Mathematics.
• Petrovic, S., Yang, Y., & Dror, M. (2007). Case-based selection of initialisation heuristics for metaheuristic examination timetabling. Expert Systems with Applications, 33(3), 772-785.
  More info

  Abstract: Examination timetabling problems are often solved by a two-phase procedure combining a sequential construction heuristic with a metaheuristic improvement search. There can be many combinations of pairing candidate construction heuristics with a metaheuristic. Different pairings are known to produce solutions of varying quality. In this paper we propose a Case Based Reasoning methodology for selecting the pairing of an appropriate sequential construction heuristic with the Great Deluge metaheuristic. We have thoroughly tested our solution approach by using extensive computational experiments in the domain of examination timetabling, and obtained the best results on a number of benchmark problems. In this research we have addressed the research issues of the representation of timetabling problems, similarity measures for timetabling problems, and the retrieval process. © 2006 Elsevier Ltd. All rights reserved.
• Bompadre, A., Dror, M., & Orlin, J. B. (2006). Improved bounds for vehicle routing solutions. Discrete Optimization, 3(4), 299-316.
  More info

  Abstract: We present lower bounds for the vehicle routing problem (VRP) with and without split deliveries, improving the well known bound of Haimovich and Rinnooy Kan. These bounds are then utilized in a design of best-to-date approximation algorithms. © 2006 Elsevier Ltd. All rights reserved.
• Dror, M., Lee, Y., Orlin, J. B., & Polishchuk, V. (2006). The TSP and the sum of its marginal values. International Journal of Computational Geometry and Applications, 16(4), 333-343.
  More info

  Abstract: This paper introduces a new notion related to the traveling salesperson problem (TSP) - the notion of the TSP ratio. The TSP ratio of a TSP instance I is the sum of the marginal values of the nodes of I divided by the length of the optimal TSP tour on I, where the marginal value of a node i ∈ 7 is the difference between the length of the optimal tour on I and the length of the optimal tour on I \i. We consider the problem of establishing exact upper and lower bounds on the TSP ratio. To our knowledge, this problem has not been studied previously. © World Scientific Publishing Company.
• Burke, E., Dror, M., Petrovic, S., & Rong, Q. u. (2005). Hybrid graph heuristics within a hyper-heuristic approach to exam timetabling problems. Operations Research/ Computer Science Interfaces Series, 29, 79-91.
  More info

  Abstract: This paper is concerned with the hybridization of two graph coloring heuristics (Saturation Degree and Largest Degree), and their application within a hyper-heuristic for exam timetabling problems. Hyper-heuristics can be seen as algorithms which intelligently select appropriate algorithms/heuristics for solving a problem. We developed a Tabu Search based hyper-heuristic to search for heuristic lists (of graph heuristics) for solving problems and investigated the heuristic lists found by employing knowledge discovery techniques. Two hybrid approaches (involving Saturation Degree and Largest Degree) including one which employs Case Based Reasoning are presented and discussed. Both the Tabu Search based hyper-heuristic and the hybrid approaches are tested on random and real-world exam timetabling problems. Experimental results are comparable with the best state-of-the-art approaches (as measured against established benchmark problems). The results also demonstrate an increased level of generality in our approach. © 2005 Springer Science+Business Media, Inc.
• Dror, M. (2005). Routing propane deliveries. Logistics Systems: Design and Optimization, 299-322.
  More info

  Abstract: This chapter is about solving the problem of propane deliveries. It is commonly viewed as a representative problem of a much larger family of hard problems of considerable practical significance. This problem has been on the front burner of the logistics academic and practitioners community for over twenty years. In this chapter I attempt to describe the practices of a propane distribution company and to summarize the literature on the more general topic of inventory routing. It is one person's point of view and I apologize ex ante for my unavoidable biases. © 2005 Springer Science+Business Media, Inc.
• Haouari, M., Chaouachi, J., & Dror, M. (2005). Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm. Journal of the Operational Research Society, 56(4), 382-389.
  More info

  Abstract: We present an exact algorithm for solving the generalized minimum spanning tree problem (GMST). Given an undirected connected graph and a partition of the graph vertices, this problem requires finding a least-cost subgraph spanning at least one vertex out of every subset. In this paper, the GMST is formulated as a minimum spanning tree problem with side constraints and solved exactly by a branch-and-bound algorithm. Lower bounds are derived by relaxing, in a Lagrangian fashion, complicating constraints to yield a modified minimum cost spanning tree problem. An efficient preprocessing algorithm is implemented to reduce the size of the problem. Computational tests on a large set of randomly generated instances with as many as 250 vertices, 1000 edges, and 25 subsets provide evidence that the proposed solution approach is very effective. © 2005 Operational Research Society Ltd. All rights reserved.
• Hartman, B. C., & Dror, M. (2005). Allocation of gains from inventory centralization in newsvendor environments. IIE Transactions (Institute of Industrial Engineers), 37(2), 93-107.
  More info

  Abstract: A company considers centrelizing a single item inventory ordering for a number of stores whose demand fluctuates randomly. First, there must be savings passed on to the store from this centralization arrangement. Then, the savings must be divided among the participating stores in a way that no store (or a subset) will have an incentive to order separately. We model this problem as a cooperative game whose players are the stores. When holding and penalty shortage costs are identical for all subsets of stores, a game base on optimal expected costs (or the corresponding benefits) is subadditive (there are savings from centralization), and for normally distributed demands, whatever their correlations the core is never empty. When the stores' holding and penalty costs differ, the corresponding game may have an empty core, and in fact, centralization may not be beneficial. We give conditions on the holding and penalty costs that ensure subadditivity. Given inventory centralization and a cost allocation game based on demand realizations, even in the case of identical holding and penalty costs the cost game in each period might gave an empty cor. We give sufficient conditions for such an allocation to be justifiable and subsidy-free (nonempty core) and examine properties of a number of exante-ex post cost allocation procedures. Copyright © "IIE".
• Hartman, B. C., & Dror, M. (2003). Optimizing centralized inventory operations in a cooperative game theory setting. IIE Transactions (Institute of Industrial Engineers), 35(3), 243-257.
  More info

  Abstract: For single period inventory models with normally distributed, correlated individual demands we examine the problem of minimizing the cost of inventory centralization as a function of the covariance matrix. In a stable centralized setting there are no incentives for any party to break-away - referred to as nonempty core conditions. For the allocated benefits in inventory centralization, nonempty core conditions are always satisfied. In this paper we discuss a step by step greedy optimization procedure which computes an optimal centralization solution. The procedure manipulates the correlations without changing the mean or the variance at each store. We do not just accept that in the centralized setting the parties are better-off, but for the first time provide the analysis of how to maximize their collective benefits.
• Knotts, G., & Dror, M. (2003). Agent-based project scheduling: Computational study of large problems. IIE Transactions (Institute of Industrial Engineers), 35(2), 143-159.
  More info

  Abstract: We present in this paper the results of a computational study for project scheduling based on new ideas for project representation taken from digital circuit technology (Knotts et al., 1998a) and a solution approach based on the artificial intelligence notion of agent technology. We experimented with projects with up to 10 000 stochastic duration activities which can be executed in a number of modes requiring renewable, nonrenewable, and periodically renewable resources. This study is about agent implementation in a project scheduling domain. It compares agent types and priority rules with respect to their impact on project schedule duration and computational performance. This work demonstrates: (i) that artificial intelligence concepts of agent technology can be successfully implemented for project scheduling; and (ii) in conducting project scheduling studies we can experiment successfully with large project networks. Both points made in this research are new.
• Jaillet, P., Bard, J. F., Huang, L., & Dror, M. (2002). Delivery cost approximations for inventory routing problems in a rolling horizon framework. Transportation Science, 36(3), 292-300.
  More info

  Abstract: The inventory routing problem considered in this paper is concerned with the repeated distribution of a commodity, such as heating oil, over a long period of time to a large number of customers. The problem involves a central depot as well as various satellite facilities which the drivers can visit during their shift to refill their vehicles. The customers maintain a local inventory of the commodity. Their consumption varies daily and cannot be predicted deterministically. In case of a stockout, a direct delivery is made and a penalty cost is incurred. In this paper, we present incremental cost approximations to be used in a rolling horizon framework for the problem of minimizing the total expected annual delivery costs.
• Anderson, R. K., & Dror, M. (2001). An interactive graphic presentation for multiobjective linear programming. Applied Mathematics and Computation, 123(2), 229-248.
  More info

  Abstract: In this paper we examine the design and implementation issues relating to the search process for a solution to an interactive multiobjective linear optimization problem (MOLP). A solution methodology proposed by Dror and Gass is employed. The primary objective of the design process is to investigate the advantages of using interactive graphics in the presentation of alternative solutions and to direct the solution search. We find several features useful, including three-dimensional perspective views, graph animation, interactive highlighting, and interactive detail inspection. © 2001 Elsevier Science Inc. All rights reserved.
• Leung, J. Y., Dror, M., & Young, G. H. (2001). Technical note: A note on an open-end bin packing problem. Journal of Scheduling, 4(4), 201-207.
  More info

  Abstract: We consider a variant of the classical one-dimensional bin packing problem, which we call the open-end bin packing problem. Suppose that we are given a list L = (p1,p2,...,pn) of n pieces, where pj denotes both the name and the size of the jth piece in L, and an infinite collection of infinite-capacity bins. A bin can always accommodate a piece if the bin has not yet reached a level of C or above, but it will be closed as soon as it reaches that level. Our goal is to find a packing that uses the minimum number of bins. In this article, we first show that the open-end bin packing problem remains strongly NP-hard. We then show that any online algorithm must have an asymptotic worst-case ratio of at least 2, and there is a simple online algorithm with exactly this ratio. Finally, we give an offline algorithm that is a folly polynomial approximation scheme with respect to the asymptotic worst-case ratio. Copyright © 2001 John Wiley & Sons Ltd.
• Dror, M., & Haouari, M. (2000). Generalized Steiner Problems and Other Variants. Journal of Combinatorial Optimization, 4(4), 415-436.
  More info

  Abstract: In this paper, we examine combinatorial optimization problems by considering the case where the set N (the ground set of elements) is expressed as a union of a finite number of m nonempty distinct subsets N1, . . . , Nm. The term we use is the generalized Steiner problems coined after the Generalized Traveling Salesman Problem. We have collected a short list of classical combinatorial optimization problems and we have recast each of these problems in this broader framework in an attempt to identify a linkage between these "generalized" problems. In the literature one finds generalized problems such as the Generalized Minimum Spanning Tree (GMST), Generalized Traveling Salesman Problem (GTSP) and Subset Bin-packing (SBP). Casting these problems into the new problem setting has important implications in terms of the time effort required to compute an optimal solution or a "good" solution to a problem. We examine questions like "is the GTSP "harder" than the TSP?" for a number of paradigmatic problems starting with "easy" problems such as the Minimal Spanning Tree, Assignment Problem, Chinese Postman, Two-machine Flow Shop, and followed by "hard" problems such as the Bin-packing, and the TSP.
• Dror, M., Haouari, M., & Chaouachi, J. (2000). Generalized spanning trees. European Journal of Operational Research, 120(3), 583-592.
  More info

  Abstract: In this paper, we propose a definition for the Generalized Minimal Spanning Tree (GMST) of a graph. The GMST requires spanning at least one node out of every set of disjoint nodes (node partition) in a graph. The analysis of the GMST problem is motivated by real life agricultural settings related to construction of irrigation networks in desert environments. We prove that the GMST problem is NP-hard, and examine a number of heuristic solutions for this problem. Computational experiments comparing these heuristics are presented.
• Hartman, B. C., Dror, M., & Shaked, M. (2000). Cores of Inventory Centralization Games. Games and Economic Behavior, 31(1), 26-49.
  More info

  Abstract: Consider a set of n stores with single-item and single-period demands. Assume an option of centralized ordering and inventory with holding and penalty costs only. In this case, a cooperative inventory "centralization" game "defines" allocations of the cost. We examine the conditions under which such an inventory centralization game has a nonempty core. We prove the existence of nonempty core for demands with symmetric distributions and the existence of nonempty core for joint multivariate normal demand distribution. We establish the equivalency of four different nonempty core conditions for the Newsboy Problem and demonstrate their efficacy for discrete independent and identically distributed (iid) demands. Journal of Economic Literature Classification Numbers: C44, C62, C71. © 2000 Academic Press.
• Knotts, G., Dror, M., & Hartman, B. C. (2000). Agent-based project scheduling. IIE Transactions (Institute of Industrial Engineers), 32(5), 387-401.
  More info

  Abstract: Agent technology offers a new way of thinking about many of the classic problems in operations research. Among these are problems such as project scheduling subject to resource constraints. In this paper, we develop and experimentally evaluate eight agent-based algorithms for solving the multimode, resource-constrained project scheduling problem. Our algorithms differ in the priority rules used to control agent access to resources. We apply our approach to a 51-activity project originally published by Maroto and Tormos. We solve the problem using two types of agent-based systems: (i) a system of simple, reactive agents that we call basic agents; and (ii) a system of more complex, deliberative agents that we call enhanced agents. Of the eight priority rules tested, we find that priority based on shortest processing time performs best in terms of schedule quality when applied by basic agents while the priority based on earliest due date performs best when applied by enhanced agents. In comparing agents across priority rules, we find that enhanced agents generate much better schedules (with makespans up to 66% shorter in some cases) and require only slightly more computation time.
• Dror, M. (1999). Polygon plate-cutting with a given order. IIE Transactions (Institute of Industrial Engineers), 31(3), 271-274.
  More info

  Abstract: This note is a complement to the paper by Hoeft and Palekar which describes the problem of cutting polygonal shapes from large plates of metal or glass. More specifically, we focus on polynomial time solvability for a number of subproblems of the more general plate-cutting problem. A primary result of this note is the polynomial time solvability for the plate-cutting problem with a given order and convex polygons.
• Dror, M., & Hartman, B. C. (1999). Special issue on game theory applications in industry: Preface. IIE Transactions (Institute of Industrial Engineers), 31(9), v-vi.
• Dror, M., Finke, G., Gravier, S., & Kubiak, W. (1999). On the complexity of a restricted list-coloring problem. Discrete Mathematics, 195(1-3), 103-109.
  More info

  Abstract: We investigate a restricted list-coloring problem. Given a graph G = (V,E), a non empty set of colors L, and a nonempty subset L(v) of L for each vertex v, find an L-coloring of G with the size of each class of colors being equal to a given integer. This restricted list-coloring problem was proposed by de Werra. We prove that this problem is script N sign P-Complete even if the graph is a path with at most two colors on each vertex list. We then give a polynomial algorithm which solves this problem for the case where the total number of colors occurring in all lists is fixed. © 1999 Elsevier Science B.V. All rights reserved.
• Dror, M., Kubiak, W., & Leung, J. Y. (1999). Tree precedence in scheduling: The strong-weak distinction. Information Processing Letters, 71(3), 127-134.
  More info

  Abstract: In this paper we formally introduce the distinction between strong and weak precedence relation in scheduling for the case of trees. We demonstrate that this distinction in precedence relation for trees (as demonstrated in earlier work for chains) is a proper one in the sense that some problems are solvable in polynomial time if weak tree relation is assumed and are NP-hard in the case of strong tree relations. For some other problems, both weak tree and strong tree relations are NP-hard, and for yet other problems both weak and strong tree relations are polynomially solvable. Since the distinction between strong and weak tree precedence was not clearly recognized in the past, this work establishes the existence of new problem categories in scheduling.
• Anastasova, K., & Dror, M. (1998). Intelligent scheduler for processing help requests on unrelated parallel machines in a computer support administration system. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, 1, 372-377.
  More info

  Abstract: This paper describes an application-oriented examination of an automated online support process for the Center of Computing and Information Technology at The University of Arizona. The online consulting activity at the Center is modeled as a set of unrelated parallel machines, the consultants, which process a stream of incoming jobs, the online help requests. Automatic Indexing, a type of Natural Language Processing, is applied to each job to estimate its machine dependent processing time. Following the time estimation scheme, we develop an online scheduling procedure whose objective is to minimize the mean flow time (reflecting perceived quality of service).
• Bard, J. F., Huang, L., Dror, M., & Jaillet, P. (1998). A branch and cut algorithm for the VRP with satellite facilities. IIE Transactions (Institute of Industrial Engineers), 30(9), 821-834.
  More info

  Abstract: An important aspect of the vehicle routing problem (VRP) that has been largely overlooked is the use of satellite facilities to replenish vehicles during a route. When possible, satellite replenishment allows the drivers to continue making deliveries until the close of their shift without necessarily returning to the central depot. This situation arises primarily in the distribution of fuels and certain retail items. When demand is random, optimizing customer routes a priori may result in significant additional costs for a particular realization of demand. Satellite facilities are one way of safeguarding against unexpected demand. This paper presents a branch and cut methodology for solving the VRP with satellite facilities subject to capacity and route time constraints. We begin with a mixed-integer linear programming formulation and then describe a series of valid inequalities that can be used to cut off solutions to the linear programming relaxation. Several separation heuristics are then outlined that are used to generate the cuts. Embedded in the methodology is a VRP heuristic for finding good feasible solutions at each stage of the computations. Results are presented for a set of problems derived from our experience with a leading propane distributor. © 1998 "IIE".
• Bard, J. F., Huang, L., Jaillet, P., & Dror, M. (1998). A decomposition approach to the inventory routing problem with satellite facilities. Transportation Science, 32(2), 189-203.
  More info

  Abstract: This paper presents a comprehensive decomposition scheme for solving the inventory routing problem in which a central supplier must restock a subset of customers on an intermittent basis. In this setting, the customer demand is not known with certainty and routing decisions taken over the short run might conflict with the long-run goal of minimizing annual operating costs. A unique aspect of the short-run subproblem is the presence of satellite facilities where vehicles can be reloaded and customer deliveries continued until the closing time is reached. Three heuristics have been developed to solve the vehicle routing problem with satellite facilities (randomized Clarke-Wright, GRASP, modified sweep). After the daily tours are derived, a parametric analysis is conducted to investigate the tradeoff between distance and annual costs. This leads to the development of the efficient frontier from which the decision maker is free to choose the most attractive alternative. The proposed procedures are tested on data sets generated from field experience with a national liquid propane distributor.
• Knotts, G., Dror, M., & Hartman, B. (1998). A project scheduling methodology derived as an analogue of digital circuit technology. Annals of Operations Research, 82, 9-27.
  More info

  Abstract: The purpose of this paper is to propose a new approach for modeling project activities and networks of project activities based on a digital circuit metaphor upon which a project scheduling tool could be built. Each activity is represented by one or more digital circuit elements where the inputs to the elements are the requirements that must be satisfied before that activity can begin. We demonstrate that our model has all the capabilities of traditional models such as PERT/CPM. We then extend our model to incorporate additional features not currently supported by most traditional models. We illustrate the use of AND, OR, NAND, NOR, and XOR gates in the creation of a project network and show how combinations of these elements can be used to represent arbitrarily complex activity requirements. Finally, we discuss how our model could be used to create an open, flexible, extendible and distributable project planning tool that supports continuous process improvement. The paper presents the model and how it was developed as an analogue of digital circuit design. Thus, it serves two audiences: those interested in the modeling process and those interested in a novel approach to project scheduling.
• Knotts, G., Dror, M., & Hartman, B. (1998). Project management tool for computer-supported cooperative work during project planning. Proceedings of the Hawaii International Conference on System Sciences, 1, 623-631.
  More info

  Abstract: This paper introduces a new conceptual approach for project management with embedded computer support for group collaboration during project planning. We propose a tool by which project planning would be initially decomposed and distributed to activity teams working independently and in parallel, to determine the requirements of the activities they have been assigned. Upon completion of this, our tool would be used to simulate the project in a group setting during which plans could be reviewed, modified, and improved. Our tool would represent a project as a distributed, dynamic process of multiple independent, interacting agents pursuing a common goal. This representation would provide deeper understanding of the nature of the project and would result in more fruitful group interaction among those participating in the planning process.
• Kubiak, W., BŁazewicz, J., Dror, M., Katoh, N., & Rock, H. (1998). Resource constrained chain scheduling of uet jobs on two machines. Operations Research, 46(5), 742-746.
  More info

  Abstract: A well-known technique for solving scheduling problems with two identical parallel processors and unit execution time jobs under a makespan minimization criteria involves finding maximum cardinality matchings in the graph associated with the problem, and then using these matchings to create optimal schedules. For some problem instances, however, this method will not work, since the problems are NP-hard. In this note, a previously open problem involving additional resource constraints is shown to have a polynomial algorithm using cardinality matching method.
• Dror, M. (1997). Chains and Trees: 'Strong'-'Weak' Order in Job Scheduling. Order, 14(3), 211-228.
  More info

  Abstract: We present a summary of recent NP-hardness and polynomial time solvability results for the distinction between 'strong' and 'weak' precedence for chains and trees in scheduling. We distinguish between chains and proper trees which are not chains, and demonstrate that the strong-weak precedence distinction for chains is not inclusive with regards to NP-hardness, and conjecture that the same holds for strong-weak tree precedence. The objective is to show that different 'interpretations' for chain and tree order relations in scheduling might have far reaching computational implications.
• Dror, M., & Langevin, A. (1997). A generalized traveling salesman problem approach to the directed clustered rural postman problem. Transportation Science, 31(2), 187-192.
  More info

  Abstract: In this paper, we examine the directed Clustered Rural Postman Problem (CRPP). The CRPP is a restricted version of the Rural Postman Problem in which each connected component of arcs to be serviced has to be completely serviced before servicing another component. We present an enumerative solution approach for the CRPP based on transforming the CRPP into a version of a Generalized Traveling Salesman Problem. This work also represents a simple yet elegant unifying view for some classes of arc and node routing problems.
• Dror, M., Kubiak, W., & Dell'Olmo, P. (1997). Scheduling chains to minimize mean flow time. Information Processing Letters, 61(6), 297-301.
  More info

  Abstract: In this note we consider the chain precedence relation in scheduling and distinguish between strong chains and weak chains. We prove that for two identical parallel processors the mean flow time problem with strong chains can be solved in polynomial time whereas for weak chains the same problem is NP-hard in the strong sense. © 1997 Elsevier Science B.V.
• Mullaseril, P. A., Dror, M., & Leung, J. (1997). Split-delivery routeing heuristics in livestock feed distribution. Journal of the Operational Research Society, 48(2), 107-116.
  More info

  Abstract: In this paper, we describe a feed distribution problem encountered on a cattle ranch in Arizona. The problem is cast as a collection of split-delivery capacitated rural postman problem with time windows on arcs. We discuss the generic problems and several heuristics. The heuristics we discuss were tested and compared favourably with the working practices on the cattle ranch.
• Tracey, M., & Dror, M. (1997). Interactive graphical computer application for large-scale cattle feed distribution management. Decision Support Systems, 19(1), 61-72.
  More info

  Abstract: In this paper we describe the development of a visual computer-based interactive management tool for feed distribution at a cattle ranch. In Operations Research terminology, the underlying problem is that of a split-delivery capacitated rural postman problem with time windows on arc. In terms of decision support, the scope of the paper is the description of a computer-based tool used to graphically present the feed distribution solution, and to facilitate the management of cattle feed related input and update operations. This system was site tested in a real cattle feed environment and received very high praise from the cattle professionals.
• Agnetis, A., Dror, M., Vakharia, A. J., & Rossi, F. (1996). Tool handling and scheduling in a two-machine flexible manufacturing cell. IIE Transactions (Institute of Industrial Engineers), 28(5), 425-437.
  More info

  Abstract: In this paper we examine the issue of tool management in a flexible manufacturing cell. The type of system considered here is typical of mechanical manufacturing, in which large metallic parts are loaded on the machines and are not moved until processing completion. The architecture of the cell is characterized by the absence of on-board tool magazines on the machines. Although this permits the continuous maintenance and inspection of the tools and typically results in cost and workspace savings, it calls for more complex tool handling procedures. We present a heuristic to address the overall problem of assigning parts to machines, sequencing parts on each machine, and synchronizing tool movements. The results indicate that our method provides near-optimal solutions in terms of makespan and mean flow time. Further, we observe that the solution procedure is at least one order of magnitude faster than the approach currently used and also results in a much better mean flow time. © 1996 "IIE".
• Dror, M., & Mullaseril, P. A. (1996). Three stage generalized flowshop: scheduling civil engineering projects. Journal of Global Optimization, 9(3-4), 321-344.
  More info

  Abstract: We model the working of a civil engineering firm concerned with land development as a three stage flexible flowshop with weak chain precedence constraints and where preemption is allowed. The scheduling objective is to minimize the total tardiness for all the projects. Since solving this problem optimally is very hard, we propose a number of heuristic scheduling procedures which are evaluated extensively on real-life data and artificial problem instances. © 1996 Kluwer Academic Publishers.
• Dror, M., & Shakun, M. F. (1996). Bifurcation and adaptation in evolutionary interactive multiobjective linear programming. European Journal of Operational Research, 93(3), 602-610.
  More info

  Abstract: This paper shows how a formal modeling framework, Evolutionary Systems Design (ESD), for evolutionary problem definition and solution, can be used for problem adaptation and restructuring in optimization problems, as developed for Multiobjective Linear Programming (MOLP). Restructuring through a heuristic controls/goals/values referral process and adaptation are discussed for interactive MOLP, and illustrated by a numerical example.
• Dror, M., & Trudeau, P. (1996). Cash flow optimization in delivery scheduling. European Journal of Operational Research, 88(3), 504-515.
  More info

  Abstract: The paper examines the inventory routing problem from the perspective of the present value of the cash flow associated with the distribution of a commodity such as propane. We analyze this problem for both deterministic and stochastic customer demands and validate our results on data from a real life distribution operation of propane. The analysis based on the present value of the cash flow indicates that optimization of propane deliveries based on efficiency/cost criteria alone will generate inferior solutions and it would be more advantageous for the company to set deliveries for a large percentage of the customers based on the present value of cash flow. In addition, in the case of stochastic demands, deliveries based on the cash flow consideration will tend to reduce the number of stockouts (i.e. improve both profit and service).
• Hartman, B. C., & Dror, M. (1996). Cost allocation in continuous-review inventory models. Naval Research Logistics, 43(4), 549-561.
  More info

  Abstract: A centralized inventory system serves a number of stores with common ownership, and thus reliable and timely information sharing. Each of them pays a share of the inventory cost, and the reward structure leaves the owners of individual stores rewarded for their individual performance. Appropriate selection of a cost allocation method is important if such a centralized system is to last. In this work we propose three necessary criteria - stability (core of a related cooperative game), justifiability (consistency of benefits with costs), and polynomial computability. For a concrete example we demonstrate that common allocation procedures may not meet all three tests, and we present a method that that meets all three criteria. This kind of cost allocation analysis helps the common management to evaluate the trade-offs in choosing an allocation scheme for the cost of inventory centralization. © 1996 John Wiley & Sons, Inc.
• Askin, R. G., Dror, M., & Vakharia, A. J. (1994). Printed circuit board family grouping and component allocation for a multimachine, open-shop assembly cell. Naval Research Logistics, 41(5), 587-608.
  More info

  Abstract: This article considers a particular printed circuit board (PCB) assembly system employing surface mount technology. Multiple, identical automatic placement machines, a variety of board types, and a large number of component types characterize the environment studied. The problem addressed is that of minimizing the makespan for assembling a batch of boards with a secondary objective of reducing the mean flow time. The approach adopted is that of grouping boards into production families, allocating component types to placement machines for each family, dividing of families into board groups with similar processing times, and the scheduling of groups. A complete setup is incurred only when changing over between board families. For the environment studied, precedence constraints on the order of component placement do not exist, and placement times are independent of feeder location. Heuristic solution procedures are proposed to create board subfamilies (groups) for which the component mounting times are nearly identical within a subfamily. Assignment of the same component type to multiple machines is avoided. The procedures use results from the theory of open-shop scheduling and parallel processor scheduling to sequence boards on machines. Note that we do not impose an open-shop environment but rather model the problem in the context of an open shop, because the order of component mountings is immaterial. Three procedures are proposed for allocating components to machines and subsequently scheduling boards on the machines. The first two procedures assign components to machines to balance total work load. For scheduling purposes, the first method groups boards into subfamilies to adhere to the assumptions of the open-shop model, and the second procedure assumes that each board is a subfamily and these are scheduled in order of shortest total processing time. The third procedure starts by forming board subfamilies based on total component simpilarity and then assigns components to validate the open-shop model. We compare the performance of the three procedures using estimated daily, two-day, and weekly production requirements by averaging quarterly production data for an actual cell consisting of five decoupled machines.
• Dror, M., Laporte, G., & Trudeau, P. (1994). Vehicle routing with split deliveries. Discrete Applied Mathematics, 50(3), 239-254.
  More info

  Abstract: This paper considers a relaxation of the classical vehicle routing problem (VRP), in which split deliveries are allowed. As the classical VRP, this problem is NP-hard, but nonetheless it seems more difficult to solve exactly. It is first formulated as an integer linear program. Several new classes of valid constraints are derived, and a hierarchy between these is established. A constraint relaxation branch and bound algorithm for the problem is then described. Computational results indicate that by using an appropriate combination of constraints, the gap between the lower and upper bounds at the root of the search tree can be reduced considerably. These results also confirm the quality of a previously published heuristic for this problem. © 1994.
• Dror, M., Smith, B. T., & Trudeau, M. (1994). Utilizing Shelve Slots: Sufficiency Conditions for Some Easy Instances of Hard Problems. Journal of Complexity, 10(2), 216-229.
  More info

  Abstract: In this paper we present a minimal set of conditions sufficient to assure the existence of a solution to a system of nonnegative linear diophantine equations. More specifically, suppose we are given a finite item set U = {u1, u2, . . ., uk} together with a "size" vi ≡ v(ui) ∈ Z+, such that vi ≠ vj for i ≠ j, a "frequency" ai ≡ a(ui) ∈ Z+, and a positive integer (shelf length) L ∈ Z+ with the following conditions: (i) L = ∏nj=1pj(pj ∈ Z+ ∀j, pj ≠ pl for j ≠ l) and vi = ∏ j∈Aipj, Ai ⊆ {l, 2, . . ., n} for i = 1, . . ., n; (ii) (Ai\{{n-ary intersection}kj=1Aj}) ∩ (Al\{{n-ary intersection}kj=1Aj}) = {circled division slash}∀i ≠ l. Note that vi|L (divides L) for each i. If for a given m ∈ Z+, ∑ni=1aivi = mL (i.e., the total size of all the items equals the total length of the shelf space), we prove that conditions (i) and (ii) are sufficient conditions for the existence of a set of integers {b11, b12, . . ., b1m, b21, . . ., bn1, . . ., bnm}⊆ N such that ∑mj=1bij = ai, i = 1, . . ., k, and ∑ki=1bijvi = L, j =1, . . ., m (i.e., m shelves of length L can be fully utilized). We indicate a number of special cases of well known NP-complete problems which are subsequently decided in polynomial time. © 1994 Academic Press. All rights reserved.
• Dror, M. (1993). Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution. European Journal of Operational Research, 64(3), 432-441.
  More info

  Abstract: In this paper we address the issue of different mathematical models for the stochastic vehicle routing problem (SVRP). This problem is inherently much more difficult than the generic deterministic vehicle routing problem (VRP) for which optimal procedures can solve only small problems. Presently, we cannot even begin optimal solution procedures for the SVRP for any problem size exceeding 3 nodes. Thus, we need to examine modeling approaches to this problem in order to exploit the structure and solution properties. We present a multistate stochastic model for the SVRP. We prove that this model has an interesting minimal graph representation in which a SVRP solution corresponds to a Hamiltonian cycle. We also present a Markov decision model for the problem, concluding with a discussion of solution prospects and directions. © 1993.
• Dror, M., Laporte, G., & Louveaux, F. V. (1993). Vehicle routing with stochastic demands and restricted failures. ZOR Zeitschrift für Operations Research Methods and Models of Operations Research, 37(3), 273-283.
  More info

  Abstract: This paper considers a class of stochastic vehicle routing problems (SVRPs) with random demands, in which the number of potential failures per route is restricted either by the data or the problem constraints. These are realistic cases as it makes little sense to plan vehicle routes that systematically fail a large number of times. First, a chance constrained version of the problem is considered which can be solved to optimality by algorithms similar to those developed for the deterministic vehicle routing problem (VRP). Three classes of SVRP with recourse are then analyzed. In all cases, route failures can only occur at one of the last k customers of the planned route. Since in general, SVRPs are considerably more intractable than the deterministic VRPs, it is interesting to note that these realistic stochastic problems can be solved as a sequence of deterministic traveling salesman problems (TSPs). In particular, when k=1 the SVRP with recourse reduces to a single TSP. © 1993 Physica-Verlag.
• Dror, M. (1992). Openshop scheduling with machine dependent processing times. Discrete Applied Mathematics, 39(3), 197-205.
  More info

  Abstract: This paper examines the openshop problem with machine dependent processing times. Two objectives are considered; minimizing the maximal completion (makespan), and minimizing the mean flow time. For this problem with the makespan criteria and the number of jobs greater or equal to the number of machines we present an O(mn) optimal algorithm and prove that the same problem with the number of jobs less than the number of machines but greater or equal three is NP-hard. We also present an O(n) optimal algorithm for this problem with mean flow time criteria but two machines only, and for a special case with m machines describe an optimal O(mn) algorithm. The three machine openshop problem with machine dependent processing times and mean flow time criteria remains open. © 1992.
• Trudeau, P., & Dror, M. (1992). Stochastic inventory routing: Route design with stockouts and route failures. Transportation Science, 26(3), 171-184.
  More info

  Abstract: The stochastic inventory routing problem involves the distribution of a commodity such as heating oil over a long period of time to a large set of customers. The customers maintain a local inventory of the commodity which they consume at a daily rate. Their consumption varies daily and seasonally and their exact demand is known only upon the arrival of the delivery vehicle. This paper presentes a detailed analysis of this problem incorporating the stochastic nature of customers' consumptions and the possibility of route failures when the actual demand on a route exceeds the capacity of a vehicle. A number of solution procedures are compared on a large set of real life data for a period of 12 consecutive weeks. The winning strategy, though computationally more expensive, provides the best system performance and reduces (almost eliminates) the stockout phenomena.
• Ben-Arieh, D., & Dror, M. (1991). Intelligent heuristic for FMS scheduling using grouping. Journal of Intelligent Manufacturing, 2(6), 387-395.
  More info

  Abstract: This paper presents an approach to scheduling production in a flexible manufacturing system (FMS) environment by employing intelligent grouping of parts which results in good schedules that are easily solvable. Scheduling production in a realistic setting represents a very hard managerial task defying exact solutions, except in very few instances. This article presents and tests a methodology which produces scheduling solutions for large problems with an average small deviation from the theoretical lower bounds. Since open-shop scheduling is the most frequently encountered scheduling discipline in FMS, we restrict the analysis to this setting. The methodology presented combines manufacturing concepts developed in the group technology context with insightful understanding of machine scheduling problems. With the increasing interest in FMS such an approach is both promising and timely. © 1991 Chapman & Hall.
• Blazewicz, J., Dror, M., & Weglarz, J. (1991). Mathematical programming formulations for machine scheduling: A survey. European Journal of Operational Research, 51(3), 283-300.
  More info

  Abstract: Machine scheduling was and still is a rich and promising field for research with applications in manufacturing, logistics, computer architecture, communications, etc. Combinatorial complexity theory has now classified the great majority of known machine scheduling problems as 'easy' or 'very hard'. However, in most cases, mathematical programming models have not accompanied the algorithmic developments for solving 'easy' scheduling problems, nor have they facilitates solutions for 'hard' problems. Nevertheless, the analysis of the mathematical programming models for some hard combinatorial problems together with their polyhedral properties has enabled important computational advances for such problems as the TSP. In order to assess the present status and the solution potential of mathematical programming formulations for machine scheduling, we have compiled a systematic, consistent survey of formulations. The discussion has been developed in tandem with the classification of a given problem's complexity, since 'solvability' (i.e., the status of a problem as P or NP-hard) generally cannot be easily assessed from the formulation itself. A number of excellent survey papers on machine scheduling have appeared over the years (see the reference list), but none of them has been focused on mathematical formulations. This survey is the first one that attempts to compile a large number of mathematical programming formulations for scheduling into a single paper to ease the task of model building and testing scheduling formulations. Both, a newcomer and experienced researcher can use it as a reference point. Ultimately, mathematical programming formulations for scheduling problems might be used as a stepping stone to computational advances for some hard problems. © 1991.
• Dror, M., Shoval, P., & Yellin, A. (1991). Multiobjective linear programming. Another DSS. Decision Support Systems, 7(3), 221-232.
  More info

  Abstract: The paper presents an interactive menu driven decision support system for Multiobjective Linear Programming (MOLP) problems. The main contribution of the system lies in the ease of interaction between the decision maker (DM) and the system which is achieved, in contrast with other systems, by DM directed construction of a weak order on system variables and objectives. In the interactive stage the DM points out which objective functions are to be improved relative to the candidate solutions presented. No tradeoff evaluations are required from the DM. In addition, priorities/preferences of variables and objectives can be modified throughout the solution process. © 1991.
• Ben-Arieh, D., & Dror, M. (1990). Part assignment to electronic insertion machines. Two machine case. International Journal of Production Research, 28(7), 1317-1327.
  More info

  Abstract: Modern electronic circuit board production typically uses computerized insertion machines to insert electronic components into circuit boards in a flow shop type of production line. This paper studies the problem of assigning components to insertion machines with the aim of maximizing output. The paper initially examines the two machine assignment case, identifying requirements sufficient to ensure an optimal solution for two technological scenarios. Moreover, it is noted that the sequencing issue of different board types in a production cycle is immaterial, given large machine capacity. Solution procedures for this components assignment problem are described and tested on data obtained from a real life industrial setting. The resulting solutions are within 0.5% from optimality.
• Dror, M. (1990). Cost allocation: the traveling salesman, binpacking, and the knapsack. Applied Mathematics and Computation, 35(2), 191-207.
  More info

  Abstract: We examine the problem of cost allocation for the traveling-salesman problem (TSP). We note the significance of a "home" city in the TSP for designing cost allocation schemes, focusing on TSPs with triangular inequality. In addition, a similar cost allocation question is stated for the binpacking and the knapsack problems. © 1990.
• Kreimer, J., & Dror, M. (1990). The monotonicity of the threshold detection probability in a stochastic accumulation process. Computers and Operations Research, 17(1), 63-71.
  More info

  Abstract: In this paper we prove for a number of distributions that the probability for the value of the sum of the first k (but not before) of i.i.d.r.v. to exceed a given value A is monotonically increasing in the range k < k* (or k < k* + 1 ) where k* = max k such that kμ ≤A. We conjecture that this monotonicity property is preserved for a much larger family of distribution functions than those examined in the paper. © 1990.
• Dror, M., Laporte, G., & Trudeau, P. (1989). Vehicle routing with stochastic demands. Properties and solution frameworks. Transportation Science, 23(3), 166-176.
  More info

  Abstract: This paper considers the vehicle routing problem with stochastic demands. The objective is to provide an overview of this problem, and to examine a variety of solution methodologies. The concepts and the main issues are reviewed along with some properties of optimal solutions. The existing stochastic mathematical programming formulations are presented and compared and a new formulation is proposed. A new solution framework for the problem using Markovian decision processes is then presented.
• Gavish, B., Trudeau, P., Dror, M., Gendreau, M., & Mason, L. (1989). Fiberoptic circuit network design under reliability constraints. IEEE Journal on Selected Areas in Communications, 7(8), 1181-1187.
  More info

  Abstract: A general mathematical model for a network design problem with reliability constraints and a revised formulation which seems particularly appropriate for fiber-optics networks is presented. Upper and lower bounding procedures based on continuous relaxations of this modified formulation are described. Preliminary computational results are reported. Limited computational results indicate a good performance of the algorithm, producing a gap between lower and upper bounds that is sufficiently small for a branch-and-bound procedure to be applicable.
• Dror, M., Einav, D., & Amir, Y. (1988). Electronic equipment test unit optimization. European Journal of Operational Research, 33(3), 262-272.
  More info

  Abstract: Given is a production line for a range of electronic equipment units. The final stations in this production line consist of testing stages (both mechanical/ electrical and computerized testing). In those testing stages different circuit boards are assembled together into test assembly-units. The test assembly-units do not in general, correspond to the final product units. The number of possible test assembly-units is large. The production line management is concerned with the number of test assembly-units and the levels of inventories of the individual circuits which remain in the testing stages of the production line and are not assembled in the final products. In this paper a case study is presented in which solutions to the assembly problem are gradually developed and tested on actual data. Linear programming is the basic modeling tool followed by an ad hoc integer rounding procedure. The computational results indicate that the solution scheme developed produces near optimal testing configurations. When examined by the line managers the proposed solutions were judged to produce a considerable improvement in the efficiency of the testing stages as compared with present practice. © 1988.
• Dror, M., Gass, S. I., & Yellin, A. (1988). Experiments with an interactive procedure for MOLP given weak orders on variables and objectives. European Journal of Operational Research, 34(1), 78-85.
  More info

  Abstract: In this paper we describe computational experiments with an interactive procedure for solving a multiobjective linear-programming model. The point of departure for this paper is the work described in Gass and Dror [4] and Dror and Gass [1] in which an interactive solution procedure is outlined. Here we describe improvements in the original procedure, as well as computational experiments, and demonstrate the procedure's ability to explore successfully the solution space of a multiobjective problem. © 1988.
• Dror, M., Trudeau, P., & Ladany, S. P. (1988). Network models for seat allocation on flights. Transportation Research Part B, 22(4), 239-250.
  More info

  Abstract: This paper examines the problem of proper (optimal) control over the seat allocation on flights. Given a heterogeneous fleet of aircraft types, multi-leg flights, a number of different passenger categories, and cancelations, an airline's objective is to devise an effective system which aids in setting the seat allocation targets for each category of passengers on each flight. This issue is analyzed by a number of authors in the context of economic, simulation based, probabilistic, and mathematical programming studies. We present an attempt to address this problem from the systems prospective emphasizing characteristics such as: passenger cancelations, multi-leg flights, and rolling tactical planning time horizon. Starting from a very simple network flow models for a single flight with a number of intermediate stops, a number of progressively complex models are presented. The airline flights and the seat allocation system are represented as a generalized network flow model (with gains/losses on arcs) with the objective of flow maximization (profit maximization). This modelling approach does not claim to replace the seat allocation approaches presented in Alstrup et al. (1985), Mayer (1976), Richter (1982), Simpson (1985a), and Wang (1983), but rather construct seat allocations utilizing some of those referenced schemes in a parameter setting mode for a large network model. The objective of this paper is not to report on computational experiments, but to present a modeling approach which seems to be promising, if somewhat speculative. © 1998.
• Schweitzer, P. J., Dror, M., & Trudeau, P. (1988). PERIODIC LOADING PROBLEM: FORMULATION AND HEURISTICS.. INFOR: Information Systems and Operational Research, 26(1), 40-62.
  More info

  Abstract: The periodic loading problem involves the allocation of periodically-occurring tasks to the time-slots of a synchronous server in such a way as to minimize the maximum utilization of any time-slot. It arises when a time-division-multiplex communications bus collects data from a collection of periodically-producing sensors, e. g. , the MIL-STD-1553 protocol. This paper formulates the problem, gives bounds on the solution, and shows it contains the minimum makespan problem, hence is NP-complete. Heuristic procedures are given and their performance illustrated on a (actual) problem for which a solution is found within 1% accuracy. In addition, an empirical study for the heuristic procedures is conducted on an extensive set of artificial problems.
• Dror, M., & Ball, M. (1987). INVENTORY/ROUTING: REDUCTION FROM AN ANNUAL TO A SHORT-PERIOD PROBLEM.. Naval Research Logistics, 34(6), 891-905.
  More info

  Abstract: The inventory-routing problem is a distribution problem in which each customer maintains a local inventory of a product such as heating oil and consumes a certain amount of that product each day. Given a central supplier, the objective is to minimize the annual delivery costs while attempting to insure that no customer runs out of the commodity at any time. In this article we present a procedure for reducing the long-term version of this problem to a single-period problem, which can be attacked using standard routing algorithms. The reduction procedure involves the definition of single-period costs that reflect long-term costs, the definition of a safety stock level and a specification of the customer subset to be considered during a single period.
• Dror, M., & Gass, S. I. (1987). Interactive scheme for a MOLP problem given two partial orders: One on variables and one on objectives. Applied Mathematics and Computation, 24(3), 195-209.
  More info

  Abstract: An interactive approach for solving a multiple objective linear programming (MOLP) problem is presented. This approach assumes that the decision maker (in contrast to the analyst) can establish a (preferential) partial order Pv on the decision variables and a partial order Po on the objective functions. The solution approach presented in this paper requires minimal additional information in its interactive stage. Results are presented for a number of tests: both conceptual development and applicability in solving specific problems have been successfully tested. © 1987.
• Dror, M., & Stulman, A. (1987). OPTIMIZING ROBOT'S SERVICE MOVEMENTS: A ONE DIMENSIONAL CASE.. Computers and Industrial Engineering, 12(1), 39-46.
  More info

  Abstract: In this paper we present a simulation based analysis of a service robot operating in a textile mill. The robot's function is to locate and service the operating units which require the servicing. The main purpose of the analysis is to determine the 'best' movement decision for the robot in each instance. We present a simple simulation experiment which clearly illustrates that an increase in production output can be realized with the help of modestly sophisticated decision rules for the robot's movement.
• Dror, M., Stern, H. I., & Lenstra, J. K. (1987). PARALLEL MACHINE SCHEDULING: PROCESSING RATES DEPENDENT ON NUMBER OF JOBS IN OPERATION.. Management Science, 33(8), 1001-1009.
  More info

  Abstract: We treat the class of n job minus m machine scheduling problems with job processing times dependent on the number of jobs being simultaneously processed in the system at any point in time. Such systems occur when jobs are assigned to multiple parallel processors driven by a common power source. In situations typical of hydraulic and pneumatic power sources the level of power delivered to each processor is inversely proportional to the number of processors simultaneously at work. Aside from the variable processing rate assumptions, the remaining assumptions on the structure of the system conform to those of the standard identical parallel processor problem without job preemption.
• Dror, M., & Levy, L. (1986). A vehicle routing improvement algorithm comparison of a "greedy" and a matching implementation for inventory routing. Computers and Operations Research, 13(1), 33-45.
  More info

  Abstract: Given an initial solution to a vehicle routing problem-(VRP)-we present three heuristic route improvement schemes based on the concept of node interchange between different routes. Three algorithms are presented together with their computational performance when applied to an inventory routing problem for 12 consecutive weekly periods. All three procedures improve the initial solution constructed by a modified Clark and Wright algorithm by over 50% as measured by the change in the value of the objective function. In two of the algorithms a minimum weight matching problem is solved repetitively. © 1986.
• Dror, M., & Trudeau, P. (1986). Stochastic vehicle routing with modified savings algorithm. European Journal of Operational Research, 23(2), 228-235.
  More info

  Abstract: A stochastic vehicle routing problem (SVRP) differs from the well known vehicle routing problem (VRP) in that the actual customer demand is not known with certainty when the vehicle routes are designed. One aspect that differentiates between these problems is the notion of route failure. Route failure indicates a situation where a vehicle cannot complete all the deliveries on a designed route because its supply is exhausted at some point along the route, before the route's demand is fully satisfied. In this paper, we illustrate the effects of route failure on the expected cost of a route, as well as the impact the direction of a designed route can have on the expected cost. In addition, we present a straight-forward modification of the Clark and Wright savings algorithm to account more fully for all the costs inherent in many real routing problems, where the customers actual demands are uncertain. © 1986.
• Dror, M., Ball, M., & Golden, B. (1985). A computational comparison of algorithms for the inventory routing problem. Annals of Operations Research, 4(1), 1-23.
  More info

  Abstract: The inventory routing problem is a distribution problem in which each customer maintains a local inventory of a product such as heating oil and consumes a certain amount of that product each day. Each day a fleet of trucks is dispatched over a set of routes to resupply a subset of the customers. In this paper, we describe and compare algorithms for this problem defined over a short planning period, e.g. one week. These algorithms define the set of customers to be serviced each day and produce routes for a fleet of vehicles to service those customers. Two algorithms are compared in detail, one which first allocates deliveries to days and then solves a vehicle routing problem and a second which treats the multi-day problem as a modified vehicle routing problem. The comparison is based on a set of real data obtained from a propane distribution firm in Pennsylvania. The solutions obtained by both procedures compare quite favorably with those in use by the firm. © 1985 J.C. Baltzer A.G., Scientific Publishing Company.
• Gass, S. I., & Dror, M. (1983). INTERACTIVE APPROACH TO MULTIPLE-OBJECTIVE LINEAR PROGRAMMING INVOLVING KEY DECISION VARIABLES.. Large Scale Systems, 5(2), 95-103.
  More info

  Abstract: This paper investigates an interactive multiple-objective linear programming problem in which the decision-maker specifies an a priori partial ordering of the key decision variables. The procedure searches over the set of efficient solutions using a composite measure of goodness involving the key decision variables and the objective functions.
• Stern, H. I., & Dror, M. (1979). Routing electric meter readers. Computers and Operations Research, 6(4), 209-223.
  More info

  Abstract: Electric utility companies employ a crew of workers who periodically visit and read the electric meters of each customer in their service area. Each reader is transported by auto from a central office to the first customer on his work list. At the end of his work shift time limit the reader is free to leave the area possibly returning home or to the central office by public bus. Taking a graph that corresponds to the city network of streets meter readers must traverse each street while moving from house to house. It is possible that dead heading may be required-back tracking over a street that has already been covered. A working tour is an open path whose reading time plus deadheading time does not exceed the work limit. The problem is to find the minimum number of working tours. Stating the problem in this manner gives us an optimization problem closely related to the M-Chinese postman problem-an edge oriented routing problem. After presenting some background on this type of problem a heuristic procedure is used to solve an example from the City of Beersheva. The solution provides a 40% reduction in the number of working tours. The paper ends with a discussion of the solution, and provides conditions under which the algorithm should have practical utility. © 1979.

Proceedings Publications

• Dror, M. (2017, March). The Development of a Smart Map for Minimum ``Exertion’’ Routing Applications. In Proceedings of HICSS 50.