-
作者：HOCHBAUM, DS; SHAMIR, R
作者单位：Rutgers University System; Rutgers University New Brunswick
摘要：A high multiplicity scheduling problem consists of many jobs which can be partitioned into relatively few groups, where all the jobs within each group are identical. Polynomial, and even strongly polynomial, algorithms for the standard scheduling problem, in which all jobs are assumed to be distinct, become exponential for the corresponding high multiplicity problem. In this paper, we study various high multiplicity problems of scheduling unit-time jobs on a single machine. We provide strongly...
-
作者：ZHENG, YS; FEDERGRUEN, A
作者单位：Columbia University
摘要：In this paper, a new algorithm for computing optimal (s, S) policies is derived based upon a number of new properties of the infinite horizon cost function c(s, S) as well as a new upper bound for optimal order-up-to levels S* and a new lower bound for optimal reorder levels S*. The algorithm is simple and easy to understand. Its computational complexity is only 2.4 times that required to evaluate a (specific) single (s, S) policy. The algorithm applies to both periodic review and continuous r...
-
作者：KOUVELIS, P; LEE, HL
作者单位：Stanford University
摘要：Loading problems of Flexible Manufacturing Systems (FMSs) have usually been formulated as an integer program with nonlinear constraints for tool magazine capacities. The nonlinearity and integer nature of the problem results in the loading problem being difficult to solve. Conventional branch-and-bound methods have been proposed, but again the solution time can easily be excessive for moderate sized problems. In this paper, we present an alternative formulation of the FMS loading problem. Such...
-
作者：THOMAS, LD
摘要：The application of commonality in a system represents an attempt to reduce costs by reducing the number of unique components. A formal method for conducting commonality analysis has not been established. This paper characterizes commonality analysis as a partitioning problem for which the solution may be approximated by the application of clustering methods. A clustering algorithm is developed and applied to a commonality analysis of Space Station water tanks. The success in applying a cluster...
-
作者：COLIN, JY; CHRETIENNE, P
作者单位：Sorbonne Universite; IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom SudParis
摘要：This paper addresses a machine scheduling problem that arises in the case of scheduling tasks over an idealized distributed multiprocessor. Precedence constraints with small communication delays have to be taken into account and task duplication is allowed. A critical path-like algorithm is presented, which is shown to construct an optimal schedule in polynomial time.
