-
作者：MOSHEIOV, G
作者单位：City University of New York (CUNY) System; Baruch College (CUNY); Hebrew University of Jerusalem
摘要：A set of N jobs has to be processed on a single machine. Jobs have the same basic processing time, but the actual processing time of each job grows linearly with its starting time. A (possibly) different rate of growth is associated with each job. We show that the optimal sequence to minimize flow time is V-shaped: Jobs are arranged in descending order of growth rate if they are placed before the minimal growth rate job, and in ascending order if placed after it. Efficient (0(N log N)) asympto...
-
作者：LOFGREN, CB; MCGINNIS, LF; TOVEY, CA
摘要：The process planning problem is described for a class of flexible assembly systems for printed circuit cards. The general Problem of minimizing the number of station visits is shown to be NP-complete, and two classes of heuristics are shown to have arbitrarily bad worst case performance. Implications for design and operating discipline are discussed.
-
作者：BOXMA, OJ; KINDERVATER, GAP
作者单位：Tilburg University; Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam
摘要：Partitioning methods lend themselves very well to implementation on parallel computers. In recent years, branch-and-bound algorithms have been tested on various types of architectures. In this paper, we develop a queueing network model for the analysis of a class of branch-and-bound algorithms on a master-slave architecture. The analysis is based on a fluid flow approximation. Numerical examples illustrate the concepts developed. Finally, related branch-and-bound algorithms are studied using a...
-
作者：VANDIJK, NM
作者单位：Vrije Universiteit Amsterdam
摘要：State-space truncation is frequently demanded for computation of large or infinite Markov chains. Conditions are given that guarantee an error bound or rate of convergence. Roughly, these conditions apply either when probabilities of large states are sufficiently small, or when transition probabilities (rates) for state increases become small in sufficiently large states. The verification of these conditions is based on establishing bounds for bias terms of reward structures. The conditions an...
