-
作者：Williamson, DP; Hall, LA; Hoogeveen, JA; Hurkens, CAJ; Lenstra, JK; Sevastjanov, SV; Shmoys, DB
作者单位：Johns Hopkins University; Eindhoven University of Technology; Cornell University; Centrum Wiskunde & Informatica (CWI)
摘要：We consider the open shop, job shop, and flow shop scheduling problems with integral processing times. We give polynomial-time algorithms to determine if an instance has a schedule of length at most 3, and show that deciding if there is a schedule of length at most 4 is NP-complete. The latter result implies that, unless P = NP. there does not exist a polynomial-time approximation algorithm for any of these problems that constructs a schedule with length guaranteed to be strictly less than 5/4...
-
作者：Bramel, J; SimchiLevi, D
作者单位：Northwestern University
摘要：The Vehicle Routing Problem with Time Windows (VRPTW) is one of the most important problems in distribution and transportation. A classical and recently popular technique that has proven effective for solving these problems is based on formulating them as a set covering problem. The method starts by solving its linear programming relaxation, via column generation, and then uses a branch and bound strategy to find an integer solution to the set covering problem: a solution to the VRPTW. An empi...
-
作者：De, P; Dunne, EJ; Ghosh, JB; Wells, CE
作者单位：Ihsan Dogramaci Bilkent University
摘要：This note addresses the discrete version of the well-known time-cost tradeoff problem for project networks, which has been studied previously in the standard project management literature as well as in the related literature on Decision-CPM, All the algorithms proposed thus far for the solution of the general problem exhibit exponential worst-case complexity, with the notable exception of the pseudo-polynomial dynamic program due to Hindelang and Muth. We first demonstrate that this algorithm ...
-
作者：Deichtmann, JM; Sainfort, F
摘要：Dyer and Sarin (1979) proposed an important generalization of the additive-multiplicative decomposition theorem for von; Neumann-Morgenstern (vNM) utility functions to measurable value functions based on the cardinality property of measurable value functions. However, because of a difference between the cardinality of measurable Value functions and the cardinality of vNM utility functions, an additional technical condition is needed, and presented here, for the decomposition theorem to hold.
-
作者：Sharifnia, A
摘要：We demonstrate the instability of the ''join-the-shortest-queue'' routing policy and the ''first-come-first-served'' dispatching policy for a multiclass single-station queuing system with multiple nonidentical servers. Although instability is demonstrated in a deterministic setting, we have found strong evidence that it is not limited to this setting. The phenomenon that leads to instability is different from the one reported recently in the literature for nonacyclic systems, namely, servers s...
-
作者：Seshadri, S; Shanthikumar, JG
作者单位：University of California System; University of California Berkeley
摘要：The problem of maximizing the production of good sets of semiconductor chips under random yield is reexamined in this paper. (A set of semiconductor chips is called a semiconductor kit.) This problem has been considered by Avram and Wein (1992) and Singh et al. (1988). To solve this problem we show that under certain combinations of assumptions the production process can be replaced by a black box The use of the black box model considerably simplifies the analysis and reduces the simulation ef...
-
作者：Bilge, U; Ulusoy, G
