-
作者：Herer, Y; Roundy, R
作者单位：Cornell University
摘要：We investigate the one warehouse multiretailer distribution problem with traveling salesman lour vehicle routing costs. Ne model the system in the framework of the more general production/distribution system with arbitrary non-negative monotone joint order costs. We develop polynomial time heuristics whose policy costs are provably close to the cost of an optimal policy. In particular, we show that given a submodular function which is close to the true order cost then we can find a power-of-tw...
-
作者：Mireault, P; Orlin, JB; Vohra, RV
作者单位：Universite de Montreal; Massachusetts Institute of Technology (MIT); University System of Ohio; Ohio State University
摘要：We consider the problem of minimizing the makespan when scheduling tasks on two uniform parallel machines, where one machine is q times as efficient on each task as is the other. We compute the maximum relative error of the LPT (largest processing time first) heuristic as an explicit function of cl. In the special case that the two machines are identical (q = 1), our problem and heuristic reduce to the problem and heuristic analyzed by Graham (1969).
-
作者：Buss, AH; Rosenblatt, MJ
作者单位：Technion Israel Institute of Technology; Washington University (WUSTL)
摘要：In this paper we deal with a stochastic project network and consider the impact of activity delay to maximize the expected present value of a project. It is shown that in certain situations, delaying the onset of an activity from its earliest start time can indeed increase the present value of a project due to the postponing of associated negative cash flows. Furthermore, a project that could otherwise be rejected (negative expected present value) may become profitable (positive expected prese...
-
作者：Li, JW
摘要：We study in this paper an approximation method for the calculation of various performance measures of a GI/G/1 queue. Instead of solving the waiting time directly, we analyze the idle-period distribution as the starting point. The result is then taken as input to many known results to gel other performance measures. We show that the distribution of the GI/G/1 idle period satisfies a nonlinear integral equation. This equation directly leads to an accurate approximate solution of the idle-period...
-
作者：Munier, A; Konig, JC
作者单位：Universite Paris Saclay
摘要：This paper addresses a scheduling problem with interprocessor communication delays: the jobs and the communication delays are of unit length. The number of processors is unbounded. The aim is to minimize the makespan. We develop a new list scheduling heuristic and we prove that its worst-case relative performance is 4/3.
-
作者：Myung, YS; Kim, HG; Tcha, DW
作者单位：Korea Advanced Institute of Science & Technology (KAIST)
摘要：In this paper we consider the Ring Loading Problem, which arises in the design of SONET bidirectional rings. The issue of demand splitting divides the ring loading problem into the two kinds. One allows a demand to be split and routed in two different directions and the other does not. The former I;ind becomes a relaxation of the latter. We present an efficient exact solution procedure for the case with demand splitting, and a two-approximation algorithm for the case without demand splitting. ...
-
作者：Lee, CY; Uzsoy, R; MartinVega, LA
作者单位：Purdue University System; Purdue University; Lehigh University
