-
作者：Kroon, LG; Salomon, M; VanWassenhove, LN
作者单位：Tilburg University; INSEAD Business School
摘要：The Tactical Fixed Interval Scheduling Problem (TFISP) is the problem of determining the minimum number of parallel nonidentical machines, such that a feasible schedule exists for a given set of jobs. In TFISP, each job must belong to a specific job class and must be carried out in a prespecified time interval. The problem is complicated by the restrictions that (1) each machine can handle only one job at a time, (2) each machine can handle only jobs from a subset of the job classes, and (3) p...
-
作者：Gendreau, M; Laporte, G; Hertz, A
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：The Traveling Salesman Problem with Backhauls (TSPB) is defined on a graph G = (V, E). The vertex set is partitioned into V = ({v(2)}, L, B), where v(1) is a depot, L. is a set of linehaul customers, and B is a set of backhaul customers. A cost matrix satisfying the triangle inequality is defined on the edge set E. The TSPB consists of determining a least-cost Hamiltonian cycle on G such that all vertices of L are visited contiguously after v(1), followed by all vertices of B. Following a resu...
-
作者：Hopp, WJ; Spearman, ML; Zhang, RQ
作者单位：University System of Georgia; Georgia Institute of Technology; University of Michigan System; University of Michigan
摘要：This work was initiated and supported by a manufacturer of mail processing equipment, which stocks 30,000 distinct parts in a distribution center to support field maintenance of their equipment. To find an effective stocking policy for this system we formulate a constrained optimization model with the objective of minimizing overall inventory investment at the distribution center subject to constraints on customer service and order frequency. Because size, integrality, and nonconvexity make th...
-
作者：Murphy, FH; Panchanadam, V
摘要：We use the models of cognitive psychology and the early literature on linear programming models to understand how experts organize their thinking about models. We show that several different patterns appear in the way models are related to each other. This paper also is a kind of cognitive history of the formulation of linear programming models in the first decade after the invention of the field.
-
作者：Lim, WS; Alpern, S; Beck, A
作者单位：University of London; London School Economics & Political Science; University of Wisconsin System; University of Wisconsin Madison
摘要：Suppose n blind. speed one, players are placed by a random permutation onto the integers 1 to n, and each is pointed randomly to the right or left. What is the least expected time required for m less than or equal to n of them to meet together at a single point? If they must all use the same strategy we call this time the symmetric rendezvous value R-n,m(s); otherwise the asymmetric value R-n,m(a). We show that R-3,2(a) = 47/48, and that R-n,n(s), is asymptotic to n/2. These results respective...
-
作者：Mingozzi, A; Bianco, L; Ricciardelli, S
作者单位：University of Rome Tor Vergata
摘要：The Traveling Salesman Problem with Time Window and Precedence Constraints (TSP-TWPC) is to find an Hamiltonian tour of minimum cost in a graph G = (X,A) of n vertices, starting at vertex 1, visiting each vertex i is an element of X during its time window and after having visited every vertex that must precede i, and returning to vertex 1. The TSP-TWPC is known to be NP-hard and has applications in many sequencing and distribution problems. In this paper we describe an exact algorithm to solve...
-
作者：Fischetti, M; Gonzalez, JJS; Toth, P
作者单位：Universidad de la Laguna; University of Padua; University of Bologna
摘要：We consider a variant of the classical symmetric Traveling Salesman Problem in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. This NP-hard problem is known in the literature as the symmetric Generalized Traveling Salesman Problem (GTSP), and finds practical applications in routing, scheduling and location-routing. In a companion paper (Fischetti et al. 1995) we modeled GTSP as an integer linear program, and studied the facial str...
-
作者：Kohl, N; Madsen, OBG
作者单位：Technical University of Denmark
摘要：Our paper presents a new optimization method for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is a generalization of the Vehicle Routing Problem, where the service of a customer must start within a given time interval-a so-called time window. Our method is based on a Lagrangian relaxation of the constraint set requiring that each customer must be serviced. The master problem consists of finding the optimal Lagrangian multipliers and the subproblem is a Shortest Path Problem...
-
作者：Lederer, PJ; Li, LD
作者单位：Yale University
摘要：This paper studies competition between firms that produce goods or services for customers sensitive to delay time. Firms compete by setting prices and production rates for each type of customer and by choosing scheduling policies. The existence of a competitive equilibrium is proved. The competitive equilibrium is well defined whether or not a firm can differentiate between customers based upon physical characteristics because each customer has incentive to truthfully reveal its delay cost. Fu...
-
作者：Hall, NG; Kamoun, H; Sriskandarajah, C
作者单位：Universite de Sfax; Universite de Gafsa; University of Toronto
摘要：This paper considers the scheduling of operations in a manufacturing cell that repetitively produces a family of similar parts on two or three machines served by a robot. We provide a classification scheme for scheduling problems in robotic cells. We discuss finding the robot move cycle and the part sequence that jointly minimize the production cycle time, or equivalently maximize the throughput rate. For multiple part-type problems in a two-machine cell, we provide an efficient algorithm that...
