-
作者：Balas, E; Carrera, MC
摘要：We discuss a branch and bound algorithm for set covering, whose centerpiece is a new integrated upper bounding/lower bounding procedure called dynamic subgradient optimization (DYNSGRAD). This new procedure, applied to a Lagrangean dual at every node of the search tree, combines the standard subgradient method with primal and dual heuristics that interact to change the Lagrange multipliers and tighten the upper and lower bounds, fix variables, and periodically restate the Lagrangean itself. Ex...
-
作者：Chen, B; Glass, CA; Potts, CN; Strusevich, VA
作者单位：University of Southampton; University of Greenwich
摘要：This paper considers the problem of sequencing n jobs in a three-machine flow shop with the objective of minimizing the makespan, which is the completion time of the last job. An O(n log n) time heuristic that is based on Johnson's algorithm is presented. It is shown to generate a schedule with length at most 5/3 times that of an optimal schedule, thereby reducing the previous best available worst-case performance ratio of 2. An application to the general flow shop is also discussed.
-
作者：Ramudhin, A; Bartholdi, JJ; Calvin, JM; Vate, JHV; Weiss, G
作者单位：Laval University; University System of Georgia; Georgia Institute of Technology
摘要：We study a two-machine flowshop in which all processing times are independently and identically distributed, with values known to the scheduler. We are able to describe in detail the expected behavior of the flowshop under optimal and heuristic schedules. Our results suggest that minimizing makespan might be a superfluous objective: random schedules are easier to construct and require significantly less intermediate storage between the machines; moreover, they are known to be asymptotically op...
-
作者：Edirisinghe, NCP
摘要：This paper develops new bounds on the expectation of a convex-concave saddle function of a random vector with compact domains. The bounds are determined by replacing the underlying distribution by unique discrete distributions, constructed using second-order moment information. The results extend directly to new second moment lower bounds in closed-form for the expectation of a convex function. These lower bounds are better than Jensen's bound, the only previously known lower bound for the con...
-
作者：Campbell, JF
摘要：Hub facilities serve as switching and transshipment points in transportation and communication networks. Hub networks concentrate flows on the hub-to-hub links and benefit from economies of scale in interhub transportation. Most hub location research has focused on problems where each origin/destination is allocated to a single hub. However, multiple allocation to more than one hub is necessary to minimize total transportation costs. This paper defines ap-hub median, analogous to ap-median, an...
-
作者：Harrison, JM; Pich, MT
作者单位：INSEAD Business School
摘要：The QNET method for two-moment analysis of multiclass open networks is extended to allow complex workstations of various types. For example, the extension described here allows one to treat stations where several unreliable machines are tended by a small number of repair technicians, or stations where several machines that require setups are tended by a small number of operators. To illustrate the general concepts, a four-station manufacturing example is discussed in detail. In the QNET method...
-
作者：Cheung, RK; Powell, WB
作者单位：Princeton University; Iowa State University
摘要：We consider the class of multistage dynamic networks with random are capacities a framework that is well suited to model dynamic fleet management problems. We propose a successive convex approximation approach that produces an approximation to the expected recourse function which captures the future effects of current decisions under uncertainty. This method decomposes the network in each stage into tree subproblems, whose expected recourse functions are easy to obtain. We also compare this me...
-
作者：Chand, S; Moskowitz, H; Novak, A; Rekhi, I; Sorger, G
作者单位：University of Vienna
摘要：Management of process improvement activities is an essential part of the manufacturing strategy of a firm to remain globally competitive in the long run. This paper considers a manufacturing environment where process improvement activities require use of the productive capacity of the firm in addition to other investments. Thus the firm must allocate its productive capacity between production activities and improvement activities. The output of production activities is used to meet customer de...
-
作者：Massey, WA; Whitt, W
摘要：In this paper we consider the M(t)/G/s/0 model, which has s servers in parallel, no extra waiting space, and i.i.d. service times that are independent of a nonhomogeneous Poisson arrival process. Arrivals finding all servers busy are blocked (lost). We consider approximations for the average blocking probabilities over subintervals (e.g., an hour when the expected service time is five minutes) obtained by replacing the nonstationary arrival process over that subinterval by a stationary arrival...
-
作者：Kimura, T
摘要：This paper develops a transform-free approximation for the steady-state queue-length distribution in an M/G/s queue with finite waiting spaces. The approximation is obtained by using a conservation law and some heuristics. It is shown that the approximation is exact for the cases with either no extra waiting space, exponential service-time distribution, or a certain two-parameter family of service-time distributions. It is also shown that the approximation has the same light-traffic properties...
