-
作者：VANLAARHOVEN, PJM; AARTS, EHL; LENSTRA, JK
作者单位：Philips; Philips Research; Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI)
摘要：We describe an approximation algorithm for the problem of finding the minimum makespan in a job shop. The algorithm is based on simulated annealing, a generalization of the well known iterative improvement approach to combinatorial optimization problems. The generalization involves the acceptance of cost-increasing transitions with a nonzero probability to avoid getting stuck in local minima. We prove that our algorithm asymptotically converges in probability to a globally minimal solution, de...
-
作者：ATKINS, D; QUEYRANNE, M; SUN, DN
摘要：An assembly production system with n facilities has a constant external demand occurring at the end facility. Production rates at each facility are finite and nonincreasing along any path in the assembly network. Associated with each facility are a setup cost and positive echelon holding cost rate. The formulation of the lot sizing problem is developed in terms of integer-ratio lot size policies. This formulation provides a unification of the integer-split policies formulation of L. B. Schwarz...
-
作者：BADINELLI, RD
摘要：In this paper, we construct a model of the steady-state values of on-hand inventory and backorders for each facility of a serial inventory system in which each facility follows a (Q, R) policy based on installation stock. Such policies are represented by the popular kanban systems as well as more conventional applications of (Q, R) policies. The descriptive model presented here is intended for optimizing the parameters of such a policy and for obtaining theoretical results about the behavior o...
-
作者：BLANC, JPC
摘要：An iterative numerical technique for the evaluation of queue length distributions is applied to multiserver systems with queues in parallel in which customers join (one of) the shortest queues upon arrival. The technique is based on power-series expansions of the state probabilities as functions of the load of the system. The convergence of the series is accelerated by applying a modified form of the epsilon algorithm. The shortest-queue model lends itself particularly well to a numerical anal...
-
作者：FAY, NA; GLAZEBROOK, KD
作者单位：Newcastle University - UK
摘要：In many contexts in which resource allocation takes place in a stochastic environment, new jobs arrive over time. Incorporation of an arrivals process into the scheduling model significantly complicates the problem of determining optimal strategies. Earlier computational studies suggest that for a large class of single machine problems often little is lost by adopting a heuristic that (essentially) ignores the arrivals process. Cases are described in which the heuristic yields an optimal strat...
-
作者：KENNINGTON, J; WANG, Z
摘要：The objective of this study is to develop a shortest augmenting path algorithm for solving the semi-assignment problem and conduct an extensive computational comparison with the best alternative approaches. The algorithm maintains dual feasibility and complementary slackness and works toward satisfying primal feasibility. Effective heuristics are used to achieve an excellent advanced start, and convergence is assured via the use of the shortest augmenting path procedure using reduced costs for...
-
作者：ROSEN, JB; XUE, GL
摘要：For the Euclidean single facility location problem, E. Weiszfeld proposed a simple iterative algorithm in 1937. Later, it was proved by numerous authors that it is a convergent descent algorithm. W. Miehle extended Weiszfeld's algorithm to solve the Euclidean multifacility location problem. Then, L. M. Ostresh proved that Miehle's algorithm is a descent algorithm. Recently, F. Rado modified Miehle's algorithm and provided several sets of sufficient conditions for the modified algorithm to conv...
-
作者：ZHENG, YS
-
作者：AHUJA, RK; ORLIN, JB
作者单位：Massachusetts Institute of Technology (MIT)
摘要：In this paper, we present a new primal simplex pivot rule and analyze the worst case complexity of the resulting simplex algorithm for the minimum cost flow, the assignment, and the shortest path problems. We consider networks with n nodes, m arcs, integral arc capacities bounded by an integer number U, and integral arc costs whose magnitudes are bounded by an integer number C. Our pivot rule may be regarded as a scaling version of Dantzig's pivot rule. Our pivot rule defines a threshold value...
-
作者：BARAHONA, F; WEINTRAUB, A; EPSTEIN, R
作者单位：Universidad de Chile
摘要：We present a model for forest planning with habitat dispersion constraints. The problem is reduced to a linear program that is solved by a column generation approach. Generating one column reduces to a stable set problem in a graph; this is solved with linear programming techniques based on a partial description of the stable set polytope. We report computational experience with medium sized problems.
