Data network을 통한 다수 클라이언트를 서비스하는 방법 = Serving multiple clients through a data network with arcs

다국어 초록 (Multilingual Abstract)

We consider the serving multiple clients through a data network with arcs having different bandwidth and delay. Bandwidth and delay are two major parameters in a data network and make the scheduling problem differ from the usual shortest path problem and maximal flow problem. We prove that this problem is NP-hard and develop a MIP(Mixed Integer Programming) model for the problem.
We propose two step approach to solve this problem. The first step is to find the quickest path for each data. Next step is to schedule all data with fixed path. We propose one optimal algorithm to find the quickest path for one server to many clients. Also we propose one heuristic to find new optimal solution for the problem with fixed path. Our computational experiment shows that proposed heuristic yields good results.

참고문헌 (Reference)

1 T Gonzalez, "Unit execution time shop problems" 7 : 57-66, 1982

2 Y. L. Chen, "The quickest path problem" 17 : 153-161, 1990

3 E.Q.V. Martins, "On a special class of bicriterion path problems" 17 : 85-94, 1984

4 S.K. Goyal, "No-Wait Shop Scheduling: Computational Complexity and Approximate Algorithms" 25 : 220-244, 1988

5 J. Du, "Minimizing mean flow time in two-machine open shops and flow shops" 14 : 24-44, 1993

6 S Sahni, "Complexity of Scheduling Shops with No Wait in Process" 4 : 448-457, 1979

7 E.Q.V. Martins, "An algorithm for the quickest path problem" 30 : 195-198, 1997