-
作者：Moulin, Herve
作者单位：Rice University
摘要：We look for protocols (service disciplines) setting an upper bound on the slowdown (expected sojourn time divided by job size) a job may face, irrespective of the processing times of other jobs. We call this worst slowdown the liability of a job. In a scheduling problem with identical release dates, allowing the server to randomize the order of service cuts almost in half the liability profiles feasible under deterministic protocols. The same is true if cash transfers are feasible and users ha...
-
作者：Nunez, Manuel A.; Garfinkel, Robert S.; Gopal, Ram D.
作者单位：University of Connecticut
摘要：Data perturbation and query restriction are two methods developed to protect confidential data in statistical databases. In the former, the data is systematically changed to yield answers to queries that are statistically similar to those that would have resulted from the original data. The latter provides exact answers to queries as long as the risk of exact disclosure of confidential data does not become too great. We present a new methodology to combine these techniques so that the advantag...
-
作者：Degraeve, Zeger; Jans, Raf
作者单位：University of London; London Business School; Erasmus University Rotterdam; Erasmus University Rotterdam - Excl Erasmus MC
摘要：Although the textbook Dantzig-Wolfe decomposition reformulation for the capacitated lot-sizing problem, as already proposed by Manne [Manne, A. S. 1958. Programming of economic lot sizes. Management Sci. 4(2) 115-135], provides a strong lower bound, it also has an important structural deficiency. Imposing integrality constraints on the columns in the master program will not necessarily give the optimal integer programming solution. Manne's model contains only production plans that satisfy the ...
-
作者：Eriksson, Kimmo; Sjoestrand, Jonas; Strimling, Pontus
作者单位：Malardalen University
摘要：In a two-sided version of the famous secretary problem, employers search for a secretary at the same time as secretaries search for an employer. Nobody accepts being put on hold, and nobody is willing to take part in more than N interviews. Preferences are independent, and agents seek to optimize the expected rank of the partner they obtain among the N potential partners. We find that in any subgame perfect equilibrium, the expected rank grows as the square root of N (whereas it tends to a con...
-
作者：Avenali, Alessandro
作者单位：Sapienza University Rome
摘要：We propose a new resolution algorithm, called resolution branch and bound (RBB), where a branch-and-bound scheme is empowered by exploiting the information contained in a family of closed subproblems, collected by a full resolution phase. In particular, we use this information to define a new branching rule that seems able to reduce the risk of incurring inappropriate branchings. We apply RBB and the proposed branching rule to the maximum weighted stable set problem, as its features allow us t...
-
作者：Duchenne, Eric; Laporte, Gilbert; Semet, Frederic
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite Polytechnique Hauts-de-France; Universite de Montreal; HEC Montreal
摘要：In the m-peripatetic salesman problem (m-PSP), the aim is to determine m edge disjoint Hamiltonian cycles of minimum total cost on a graph. This article introduces new valid inequalities and polyhedral results for the m-PSP. An improved 2-index branch-and-cut algorithm is developed. Tests performed on randomly generated and TSPLIB Euclidean instances indicate that this algorithm can solve instances with more than double the size of what was previously achievable.
-
作者：Wang, Jiarnin
作者单位：Long Island University; Long Island University Post; Southwest Jiaotong University
摘要：This study extends the classical network median problem by considering the stochastic nature of demand. Assuming that the demand weights associated with nodes are independent discrete random variables, we introduce a chance-constrained programming model to define a beta-reliable median of the network. It is shown that the P-reliable median problem is NP-hard. Exact solution procedures and a normal approximation algorithm are developed to search for the beta-reliable median. Their performance i...
-
作者：Zhuang, Jun; Bier, Vicki M.
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：In this paper, we apply game theory to identify equilibrium strategies for both attacker and defender in a fully endogenous model of resource allocation for countering terrorism and natural disasters. The key features of our model include balancing protection from terrorism and natural disasters, and describing the attacker choice by a continuous level of effort rather than a discrete choice (i.e., attack or not). Interestingly, in a sequential game, increased defensive investment can lead an ...
-
作者：Viswanathan, S.
作者单位：Nanyang Technological University
摘要：We develop an algorithm for determining the highest among the class of lower bounds proposed by Atkins and Iyogun (1988) for the joint replenishment problem (JRP) with stochastic demands. The proposed algorithm is simple and does not require many more calculations than an existing lower bound based on equalization of expected runout times.
-
作者：Yunes, Tallys H.; Napolitano, Dominic; Scheller-Wolf, Alan; Tayur, Sridhar
作者单位：University of Miami; Deere & Company; Carnegie Mellon University
摘要：John Deere & Company (Deere), one of the world's leading producers of machinery, manufactures products composed of various features, within which a customer may select one of a number of possible options. On any given Deere product line, there may be tens of thousands of combinations of options (configurations) that are feasible. Maintaining such a large number of configurations inflates overhead costs; consequently, Deere wishes to reduce the number of configurations from their product lines ...
