-
作者：Glass, CA; Gupta, JND; Potts, CN
作者单位：University of Southampton; Ball State University
摘要：This paper considers the no-wait scheduling of n jobs in a two-machine flow shop, where some jobs require processing on the first machine only. The objective is to minimize the maximum completion time, or makespan. In view of its NP-hardness, we propose and analyze heuristic algorithms. Our main result is an O(n log n)-time heuristic which generates a schedule with makespan no more than 4/3 times that of an optimal schedule. This heuristic solves optimally the subproblem involving the jobs wit...
-
作者：Denuit, M; Lefèvre, C; Utev, S
作者单位：Universite Libre de Bruxelles; La Trobe University
摘要：Several new classes of discrete stochastic orderings are introduced for comparing discrete random variables that are valued in an arbitrary ordered finite grid of nonnegative points. These order relations correspond to particular cases of integral stochastic orderings which are generated by different classes of functions of convex/concave-type defined on the grid. They are natural extensions from equidistant to arbitrary grids of various orderings familiar in the literature. The main question ...
-
作者：Pisaruk, NN
作者单位：Belarusian State University
摘要：We study the mean cost cyclical game in a more general setting than that in Gurvitch et al. (1988) and Karzanow and Lebedev (1993). The game is played on a directed graph and generalizes the single source shortest. path problem. the minimum mean cycle problem (see Karp 1978), and the ergodic extension of matrix games (Moulin 1976). We prove the existence of a solution in uniform stationary strategies and present an algorithm for finding such optimal strategies. In fact, our algorithm is an ext...
