若干网络排序问题的算法和复杂性研究
|
摘要
本文从算法和复杂性的角度对一些网络排序问题进行了研究。经典的排序模型假设所有任务和资源(通常称为工件和机器)位于同一场所,从而不需要考虑工件的运输时间或机器的旅行时间。然而,在实际的应用中经常需要考虑如何对分散的任务合理地分配资源以实现资源的最优配置。在网络排序问题(Routing Scheduling Problem)中,工件分散在网络中且位置固定,机器移动或旅行到工件所在的位置进行加工。网络排序问题可分为单机VSP (Vehicle Scheduling Problem)问题、平行机VSP问题和网络作业排序问题。在VSP问题中,若所有工件的加工时间都等于零时,就得到了VRP问题(Vehicle Routing Problem)。
第二章讨论线形网络上的VRP问题。对于无准备时间约束的情形,分别给出了极小化一般正则求和目标函数和一般正则瓶颈目标函数的单机问题的拟多项式和多项式算法,并将其推广到平行机问题。特别地,给出了极小化延误工件数的单机问题的多项式算法,并证明了极小化加权延误工件数和加权总延误的单机问题都是NP困难的,但是当所有工件的工期相同时这两个问题都是多项式可解的。对于有准备时间约束的情形,给出了极小化时间表长的返回型和不返回型平行机问题的多项式算法。
第三章讨论线形网络上有准备时间约束的极小化时间表长的单机VSP问题。对于返回型问题给出了3／2-近似算法并证明了其紧性；对于不返回型问题给出了5／3-近似算法并证明了其紧性。
第四章讨论一般网络上的两个VRP问题,即在线不返回型TSP和QTSP。对于在线不返回型TSP,给出了竞争比为2~1/2+ρ的多项式算法,对于在线QTSP和在线不返回型QTSP,都给出了竞争比为1+ρ的多项式算法,其中ρ分别为求解最短Hamilton路问题、QTSP和不返回型QTSP的近似算法的性能比。此外,还给出了QTSP和不返回型QTSP的近似算法。
第五章讨论机器起点相同的极小化时间表长的网络作业排序问题。对于一般网络上的自由作业排序问题,分别对两台机器的返回型和不返回型问题给出了5／3-近似算法和7／4-近似算法,其中前一个算法是紧的；对m-台机器的问题也给出了近似算法。对于树形网络上的两台机器流水作业排序问题,证明了返回型和不返回型问题都是NP困难的,并且对返回型问题设计了10／7-近似算法。
In this thesis we study the algorithms and complexity of some routing scheduling problems. In classical scheduling problems, it is assumed that all the tasks and re-sources(also called jobs and machines) are located at the same site and hence neither transportation time for jobs nor travel time for machines is considered. However, in many practical applications we are required to optimize the allocation of resources to tasks distributed at different sites of a real or virtual network. In routing scheduling problems, the locations of the jobs are fixed and the machines travel along the network to process the jobs. Routing scheduling problems consist of single-vehicle scheduling problems, parallel-vehicle scheduling problems and routing shop scheduling problems. In vehicle scheduling problems, if each job has zero processing time we have vehicle routing problems.
In Chapter 2 we consider vehicle routing problems on a line. When no release time constraint is imposed, we give pseudo-polynomial and polynomial algorithms for single-vehicle problems with general minsum objective and general minmax objective respectively, and generalized them to parallel-vehicle problems. Particularly, we give a polynomial algorithm for the problem of minimizing number of late jobs. For the single-vehicle problems of minimizing weighted number of late jobs and total weighted tardiness, we prove that they are both NP-hard, but when all the jobs have a common due date these two problems are both polynomially solvable. When release time constraints are imposed, we give polynomial algorithms for two versions of the parallel-vehicle problem of minimizing makespan.
In Chapter 3 we discuss the single-vehicle scheduling problem of minimizing makespan with release time constraints on a line. For the tour-version problem we propose 3/2-approximation algorithm and give tight examples. For the path-version problem, we present 5/3-approximation and also show tight examples.
In Chapter 4 we deal with two vehicle routing problems on a graph, i.e., the path-version of TSP and Quota Traveling Salesman Problem(QTSP). We give a ((?)+ρ)- competitive polynomial algorithm for the path-version of online TSP and (1+ρ)-competitive polynomial algorithms for both online QTSP and its path-version counterpart, whereρdenotes the approximation ratio for the Shortest Hamiltonian Path Problem, QTSP and the path-version of QTSP respectively. Moreover, we also develop approximation algo-rithms for QTSP and its path version counterpart.
In Chapter 5, we treat the routing shop scheduling problems of minimizing makespan in which all the machines have the same initial location. For open shop problems on a graph, we obtain a 5/3-approximation algorithm and a 7/4-approximation algorithm for the tour-version and path-version of two machine problem respectively, and the former is tight. These algorithms are generalized to m-machine problem. For two-machine flow shop problem on a tree, we prove both tour-version and path-version are NP-hard and give a 10/7-approximation algorithm for the tour-version.
第二章讨论线形网络上的VRP问题。对于无准备时间约束的情形,分别给出了极小化一般正则求和目标函数和一般正则瓶颈目标函数的单机问题的拟多项式和多项式算法,并将其推广到平行机问题。特别地,给出了极小化延误工件数的单机问题的多项式算法,并证明了极小化加权延误工件数和加权总延误的单机问题都是NP困难的,但是当所有工件的工期相同时这两个问题都是多项式可解的。对于有准备时间约束的情形,给出了极小化时间表长的返回型和不返回型平行机问题的多项式算法。
第三章讨论线形网络上有准备时间约束的极小化时间表长的单机VSP问题。对于返回型问题给出了3／2-近似算法并证明了其紧性；对于不返回型问题给出了5／3-近似算法并证明了其紧性。
第四章讨论一般网络上的两个VRP问题,即在线不返回型TSP和QTSP。对于在线不返回型TSP,给出了竞争比为2~1/2+ρ的多项式算法,对于在线QTSP和在线不返回型QTSP,都给出了竞争比为1+ρ的多项式算法,其中ρ分别为求解最短Hamilton路问题、QTSP和不返回型QTSP的近似算法的性能比。此外,还给出了QTSP和不返回型QTSP的近似算法。
第五章讨论机器起点相同的极小化时间表长的网络作业排序问题。对于一般网络上的自由作业排序问题,分别对两台机器的返回型和不返回型问题给出了5／3-近似算法和7／4-近似算法,其中前一个算法是紧的；对m-台机器的问题也给出了近似算法。对于树形网络上的两台机器流水作业排序问题,证明了返回型和不返回型问题都是NP困难的,并且对返回型问题设计了10／7-近似算法。
In this thesis we study the algorithms and complexity of some routing scheduling problems. In classical scheduling problems, it is assumed that all the tasks and re-sources(also called jobs and machines) are located at the same site and hence neither transportation time for jobs nor travel time for machines is considered. However, in many practical applications we are required to optimize the allocation of resources to tasks distributed at different sites of a real or virtual network. In routing scheduling problems, the locations of the jobs are fixed and the machines travel along the network to process the jobs. Routing scheduling problems consist of single-vehicle scheduling problems, parallel-vehicle scheduling problems and routing shop scheduling problems. In vehicle scheduling problems, if each job has zero processing time we have vehicle routing problems.
In Chapter 2 we consider vehicle routing problems on a line. When no release time constraint is imposed, we give pseudo-polynomial and polynomial algorithms for single-vehicle problems with general minsum objective and general minmax objective respectively, and generalized them to parallel-vehicle problems. Particularly, we give a polynomial algorithm for the problem of minimizing number of late jobs. For the single-vehicle problems of minimizing weighted number of late jobs and total weighted tardiness, we prove that they are both NP-hard, but when all the jobs have a common due date these two problems are both polynomially solvable. When release time constraints are imposed, we give polynomial algorithms for two versions of the parallel-vehicle problem of minimizing makespan.
In Chapter 3 we discuss the single-vehicle scheduling problem of minimizing makespan with release time constraints on a line. For the tour-version problem we propose 3/2-approximation algorithm and give tight examples. For the path-version problem, we present 5/3-approximation and also show tight examples.
In Chapter 4 we deal with two vehicle routing problems on a graph, i.e., the path-version of TSP and Quota Traveling Salesman Problem(QTSP). We give a ((?)+ρ)- competitive polynomial algorithm for the path-version of online TSP and (1+ρ)-competitive polynomial algorithms for both online QTSP and its path-version counterpart, whereρdenotes the approximation ratio for the Shortest Hamiltonian Path Problem, QTSP and the path-version of QTSP respectively. Moreover, we also develop approximation algo-rithms for QTSP and its path version counterpart.
In Chapter 5, we treat the routing shop scheduling problems of minimizing makespan in which all the machines have the same initial location. For open shop problems on a graph, we obtain a 5/3-approximation algorithm and a 7/4-approximation algorithm for the tour-version and path-version of two machine problem respectively, and the former is tight. These algorithms are generalized to m-machine problem. For two-machine flow shop problem on a tree, we prove both tour-version and path-version are NP-hard and give a 10/7-approximation algorithm for the tour-version.
引文
[1]S. Cook, The complexity of theorem proving procedures, in:Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, ACM-Press, New York,1971, 151-158.
[2]R. Karp, Reducibility among combinatorial problems, in:Complexity of Computer Computations, edited by R. Miller and J. Thatcher, Plenum Press, New York,1972, 85-103.
[3]A. Fiat, G.J. Woeginger (eds.), Online Algorithms:The State of the Art. Springer, 1998.
[4]F. Afrati, S. Cosmadakis, C.H. Papadimitriou, G. Papageorgiou, N. Papakostanti-nou, The complexity of the traveling repairman problem. Informatique Theorique et Applications,1986,20(1):79-87.
[5]H. Psaraftis, M. Solomon, T. Magnanti, T.-U. Kim, Routing and scheduling on a shoreline with release times. Management Science,1990,36:212-223.
[6]I. Averbakh, O. Berman, Routing two-machine flowshop problems on networks with special structure. Transportation Science,1996,30:303-314.
[7]I. Averbakh, O. Berman, A simple heuristic for m-machine flow-shop and its ap-plications in routing-scheduling problems. Operations Research,1999,47:165-170.
[8]J.N. Tsitsiklis, Special cases of traveling salesman and repairman problems with time windows. Networks,1992,22:263-282.
[9]Y. Karuno, H. Nagamochi, T. Ibaraki, Vehicle scheduling on a tree to minimize maximum lateness. Journal of Operations Research Society of Japan,1996,39: 345-355.
[10]Y. Karuno, H. Nagamochi, T. Ibaraki, Vehicle scheduling on a tree with release and handling times. Annals of Operations Research,1997,69:193-207.
[11]M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research,1987,35:254-265.
[12]M. Solomon, J. Desrosiers, Time window constrained routing and scheduling prob-lems. Transportation Science,1988,22:1-13.
[13]B.L. Golden, S. Raghavan, E.A. Wasil (eds.), The Vehicle Routing Problem:Latest Advances and New Challenges. Springer,2008.
[14]E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequencing and scheduling:algorithms and complexity. In:S.C. Graves, A.H.G. Rinnooy Kan, P. Zipkin (eds.), Handbooks in Operations Research and Management Science, Vol.4, Logistics of Production and Inventory, North-Holland, Amsterdam,1993,445-522.
[15]I. Averbakh,0. Berman, Routing and location-routing p-delivery men problems on a path. Transportation Science,1994,28:162-166.
[16]D. Simchi-Levi,0. Berman, Minimizing the total flow time of n jobs on a network. HE Transactions,1991,23:236-244.
[17]B. Wu, Polynomial time algorithms for some minimum latency problems. Information Processing Letters,2000,75:225-229.
[18]A. Garcia, P. Jodra, J. Tejel, A note on the traveling repairman problem. Net-works,2002,40:27-31.
[19]A. Garcia, P. Jodra. J. Tejel, An efficient algorithm for on-line searching of min-ima in Monge path-decomposable tridimensional arrays. Information Processing Let-ters,1998,68:3-9.
[20]R.A. Sitters, Complexity and approximation in routing and scheduling. PhD thesis, Technische Universiteit Eindhoven,2004.
[21]G.H. Young, C. Chen, Single-vehicle scheduling with time window constraints. Jour-nal of Scheduling,1999,2:175-187.
[22]Y. Karuno, H. Nagamochi, T. Ibaraki, A 1.5-approximation for single vehicle schedul-ing problem on a line with release and handling times. In:Proc. ISCIE/ASME 1998 Japan-USA Symposium on Flexible Automation,1998,3:1363-1368.
[23]Y. Karuno, H. Nagamochi, T. Ibaraki, Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks. Networks,2002,39:203-209.
[24]D.R. Gaur, A. Gupta, R. Krishnamurti, A (?)-approximation algorithm for schedul-ing vehicles on a path with release and handling times. Information Processing Let-ters,2003,86:87-91.
[25]B. Bhattacharya, P. Carmi, Y. Hu, Q. Shi, Single vehicle scheduling problems on path/tree/cycle networks with release and handling times. Lecture Notes in Com-puter Science,2008,5369:800-811.
[26]W.E. de Paepe, J.K. Lenstra, J. Sgall, R.A. Sitters, L. Stougie, Computer-aided complexity classification of dial-a-ride problems. INFORMS Journal on Comput-ing,2004,16:120-132.
[27]H. Nagamochi, K. Mochizuki, T. Ibaraki, Complexity of the single vehicle scheduling problems on a graphs. Information Systems and Operations Research,1997,35: 256-276.
[28]J.E. Augustine, S. Seiden, Linear time approximation schemes for vehicle scheduling problems. Theoretical Computer Science,2004,324:147-160.
[29]E. Minieka, The delivery man problem on a tree network. Annals of Operations Research,1989,18:261-266.
[30]R. Sitters, The minimum latency problem is NP-hard for weighted trees, in:Proc. 9th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2002, pp.230-239.
[31]I. Averbakh, O. Berman, Sales-delivery man problems on treelike networks. Net-works,1995,25:45-58.
[32]N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh,1976.
[33]J.A. Hoogeveen, Analysis of Christofide's heuristic:some paths are more difficult than cycles. Operations Research Letters,1991,10:291-295.
[34]B. Awerbuch, Y. Azar, A. Blum, S. Vempala, New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM Journal on Comput-ing,1998,28:254-262.
[35]G. Ausiello, S. Leonardi, A. Marchetti-Spaccamela, On salesmen, repairmen, spi-ders, and other traveling agents, in:G. Bongiovanni, G. Gambosi, R. Petreschi (Eds.), Proc.4th Italian Conf. on Algorithms and Complexity, in:Lecture Notes in Computer Science, vol.1767, Springer-Verlag,2000, pp.1-16.
[36]M.X. Goemans, D.P. Williamson, A general approximation technique for constrained forest problems. SIAM Journal on Computing,1995,24:296-317.
[37]G. Ausiello, V. Bonifaci, L. Laura, The online prize-collecting traveling salesman problem. Technical Report TR 08-06, Department of Computer and Systems Science, University of Rome "La Sapienza", Rome,Italy,2006.
[38]G. Ausiello, V. Bonifaci, L. Laura, The online prize-collecting traveling salesman problem. Information Processing Letters,2008,107:199-204.
[39]K. Chaudhuri, B. Godfrey, S. Rao, K. Talwar, Paths, tours, and minimum latency tours. in:Proc.44th IEEE Symposium on Foundations of Computer Science (FOCS), 2003, pp.36-45.
[40]S. Coene, F.C.R. Spieksma, Profit-based latency problems on the line. Operations Research Letters,2008,36:333-337.
[41]Y. Karuno, H. Nagamochi,2-approximation algorithms for the multi-vehicle schedul-ing problem on a path with release and handling times. Discrete Applied Mathemat-ics,2003,129:433-447.
[42]Y. Karuno, H. Nagamochi, An approximability result of the multi-vehicle schedul-ing problem on a path with release and handling times. Theoretical Computer Sci-ence,2004,312:267-280.
[43]I. Averbakh, O. Berman, A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree. Discrete Applied Mathematics,1996,68:17-32.
[44]I. Averbakh, O. Berman, (p-1)/(p+1)-approximate algorithm for p-traveling sales-men problems on a tree with minmax objective. Discrete Applied Mathemat-ics,1997,75:201-216.
[45]H. Nagamochi, K. Okada, A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree. Discrete Applied Mathematics,2004,140: 103-114.
[46]H. Nagamochi, K. Okada, Polynomial time 2-approximation algorithms for the min-max subtree cover problem. Lecture Notes in Computer Science,2003,2906:138-147.
[47]G.N. Frederickson, M.S. Hecht, C.E. Kim. Approximation algorithms for some rout-ing problems. SIAM Journal on Computing,1978,7(2):178-193.
[48]I. Averbakh, O. Berman, I. D. Chernykh, The routing open-shop problem on a network:complexity and approximation, Working Paper, The Rotman School of Management, University of Toronto,2002.
[49]I. Averbakh, O. Berman, I. D. Chernykh, A 6/5-approximation algorithm for the two-machine routing open-shop problem on a 2-node network. European Journal of Operational Research,2005,166:3-24.
[50]I. Averbakh, O. Berman, I. D. Chernykh, The routing open-shop problem on a network:Complexity and approximation. European Journal of Operational Re-search,2006,173:531-539.
[51]G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, M. Talamo, Algorithms for the on-line traveling salesman. Algorithmica,2001.29:560-581.
[52]M. Lipmann, On-line routing problems. PhD Thesis, Technische Universiteit Eind-hoven,2003.
[53]V. Bonifaci, Models and algorithms for online server routing. PhD thesis, Technische Universiteit Eindhoven,2007.
[54]P. Jaillet, M. R. Wagner, Online routing problems:value of advanced information as improved competitive ratios. Transportation Science,2006,40(2):200-210.
[55]G. Ausiello, M. Demange, L. Laura, V. Paschos, Algorithms for the on-line quota traveling salesman problem. Information Processing Letters.2004,92:89-94.
[56]N. Ascheuer, S.O. Krumke, J. Rambau. Online dial-a-ride problems:minimizing the completion time. In:H. Reichel and S. Tison, editors, Proc.17th Symp. on Theoretical Aspects of Computer Science, volume 1770 of Lecture Notes in Computer Science, pages 639-650, Springer-Verlag,2000.
[57]E. Feuerstein, L. Stougie, On-line single-server dial-a-ride problems. Theoretical Computer Science,2001,268:91-105.
[58]S.O. Krumke, W.E. de Paepe, D. Poensgen, L. Stougie, News from the online trav-eling repairman. Theoretical Computer Science,2003,295(1-3):279-294.
[59]C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization. Prentice Hall, Engle-wood Cliffs,1982.
[60]M.R. Garey, D.S. Johnson, Computers and Intractability:A Guide to the Theory of NP-completeness. Freeman, San Francisco,1979.
[61]B. Korte, J. Vygen, Combinatorial Optimization:Theory and Algorithms. Springer, 2007.
[62]P. Brucker, Scheduling Algorithms. Springer,1995.
[63]M. Pinedo, Scheduling:Theory, Algorithms, and Systems. Springer,2001.
[64]B. Chen, C.N. Potts, G.J. Woeginger, A review of machine scheduling:complexity, algorithms and approximability. In:D.-Z. Du, P.M. Pardalos (eds.), Handbook of Combinatorial Optimization, Vol.3, Kluwer Academic Publisher,1998,21-169.
[65]唐国春,张峰,罗守成,刘丽丽,现代排序论,上海科学普及出版社,2003.
[66]V.V. Vazirani, Approximation Algorithms. Springer,2001.
[67]G. Gutin, A.P. Punnen (eds.), The Traveling Salesman Problem and Its Variations. Kluwer Academic Publisher,2002.
[68]R. Bar-Yehuda, G. Even, S. Shahar, On approximating a geometric prize-collecting traveling salesman problem with time windows. Journal of Algorithms,2005.55: 76-92.
[69]F.A. Chudak, T. Roughgarden, D.P. Williamson, Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Mathematical Programming,2004,100:411-421.
[70]T. Gonzalez, S. Sahni, Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery,1976,23:665-679.
[71]俞文鱼此,刘朝晖.两台机器若干作业问题的双向排序法.华东理工大学学报.1999,25(6)：629-633.
[72]S.M. Johnson, Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly,1954,1:61-68.
[2]R. Karp, Reducibility among combinatorial problems, in:Complexity of Computer Computations, edited by R. Miller and J. Thatcher, Plenum Press, New York,1972, 85-103.
[3]A. Fiat, G.J. Woeginger (eds.), Online Algorithms:The State of the Art. Springer, 1998.
[4]F. Afrati, S. Cosmadakis, C.H. Papadimitriou, G. Papageorgiou, N. Papakostanti-nou, The complexity of the traveling repairman problem. Informatique Theorique et Applications,1986,20(1):79-87.
[5]H. Psaraftis, M. Solomon, T. Magnanti, T.-U. Kim, Routing and scheduling on a shoreline with release times. Management Science,1990,36:212-223.
[6]I. Averbakh, O. Berman, Routing two-machine flowshop problems on networks with special structure. Transportation Science,1996,30:303-314.
[7]I. Averbakh, O. Berman, A simple heuristic for m-machine flow-shop and its ap-plications in routing-scheduling problems. Operations Research,1999,47:165-170.
[8]J.N. Tsitsiklis, Special cases of traveling salesman and repairman problems with time windows. Networks,1992,22:263-282.
[9]Y. Karuno, H. Nagamochi, T. Ibaraki, Vehicle scheduling on a tree to minimize maximum lateness. Journal of Operations Research Society of Japan,1996,39: 345-355.
[10]Y. Karuno, H. Nagamochi, T. Ibaraki, Vehicle scheduling on a tree with release and handling times. Annals of Operations Research,1997,69:193-207.
[11]M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research,1987,35:254-265.
[12]M. Solomon, J. Desrosiers, Time window constrained routing and scheduling prob-lems. Transportation Science,1988,22:1-13.
[13]B.L. Golden, S. Raghavan, E.A. Wasil (eds.), The Vehicle Routing Problem:Latest Advances and New Challenges. Springer,2008.
[14]E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequencing and scheduling:algorithms and complexity. In:S.C. Graves, A.H.G. Rinnooy Kan, P. Zipkin (eds.), Handbooks in Operations Research and Management Science, Vol.4, Logistics of Production and Inventory, North-Holland, Amsterdam,1993,445-522.
[15]I. Averbakh,0. Berman, Routing and location-routing p-delivery men problems on a path. Transportation Science,1994,28:162-166.
[16]D. Simchi-Levi,0. Berman, Minimizing the total flow time of n jobs on a network. HE Transactions,1991,23:236-244.
[17]B. Wu, Polynomial time algorithms for some minimum latency problems. Information Processing Letters,2000,75:225-229.
[18]A. Garcia, P. Jodra, J. Tejel, A note on the traveling repairman problem. Net-works,2002,40:27-31.
[19]A. Garcia, P. Jodra. J. Tejel, An efficient algorithm for on-line searching of min-ima in Monge path-decomposable tridimensional arrays. Information Processing Let-ters,1998,68:3-9.
[20]R.A. Sitters, Complexity and approximation in routing and scheduling. PhD thesis, Technische Universiteit Eindhoven,2004.
[21]G.H. Young, C. Chen, Single-vehicle scheduling with time window constraints. Jour-nal of Scheduling,1999,2:175-187.
[22]Y. Karuno, H. Nagamochi, T. Ibaraki, A 1.5-approximation for single vehicle schedul-ing problem on a line with release and handling times. In:Proc. ISCIE/ASME 1998 Japan-USA Symposium on Flexible Automation,1998,3:1363-1368.
[23]Y. Karuno, H. Nagamochi, T. Ibaraki, Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks. Networks,2002,39:203-209.
[24]D.R. Gaur, A. Gupta, R. Krishnamurti, A (?)-approximation algorithm for schedul-ing vehicles on a path with release and handling times. Information Processing Let-ters,2003,86:87-91.
[25]B. Bhattacharya, P. Carmi, Y. Hu, Q. Shi, Single vehicle scheduling problems on path/tree/cycle networks with release and handling times. Lecture Notes in Com-puter Science,2008,5369:800-811.
[26]W.E. de Paepe, J.K. Lenstra, J. Sgall, R.A. Sitters, L. Stougie, Computer-aided complexity classification of dial-a-ride problems. INFORMS Journal on Comput-ing,2004,16:120-132.
[27]H. Nagamochi, K. Mochizuki, T. Ibaraki, Complexity of the single vehicle scheduling problems on a graphs. Information Systems and Operations Research,1997,35: 256-276.
[28]J.E. Augustine, S. Seiden, Linear time approximation schemes for vehicle scheduling problems. Theoretical Computer Science,2004,324:147-160.
[29]E. Minieka, The delivery man problem on a tree network. Annals of Operations Research,1989,18:261-266.
[30]R. Sitters, The minimum latency problem is NP-hard for weighted trees, in:Proc. 9th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2002, pp.230-239.
[31]I. Averbakh, O. Berman, Sales-delivery man problems on treelike networks. Net-works,1995,25:45-58.
[32]N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh,1976.
[33]J.A. Hoogeveen, Analysis of Christofide's heuristic:some paths are more difficult than cycles. Operations Research Letters,1991,10:291-295.
[34]B. Awerbuch, Y. Azar, A. Blum, S. Vempala, New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM Journal on Comput-ing,1998,28:254-262.
[35]G. Ausiello, S. Leonardi, A. Marchetti-Spaccamela, On salesmen, repairmen, spi-ders, and other traveling agents, in:G. Bongiovanni, G. Gambosi, R. Petreschi (Eds.), Proc.4th Italian Conf. on Algorithms and Complexity, in:Lecture Notes in Computer Science, vol.1767, Springer-Verlag,2000, pp.1-16.
[36]M.X. Goemans, D.P. Williamson, A general approximation technique for constrained forest problems. SIAM Journal on Computing,1995,24:296-317.
[37]G. Ausiello, V. Bonifaci, L. Laura, The online prize-collecting traveling salesman problem. Technical Report TR 08-06, Department of Computer and Systems Science, University of Rome "La Sapienza", Rome,Italy,2006.
[38]G. Ausiello, V. Bonifaci, L. Laura, The online prize-collecting traveling salesman problem. Information Processing Letters,2008,107:199-204.
[39]K. Chaudhuri, B. Godfrey, S. Rao, K. Talwar, Paths, tours, and minimum latency tours. in:Proc.44th IEEE Symposium on Foundations of Computer Science (FOCS), 2003, pp.36-45.
[40]S. Coene, F.C.R. Spieksma, Profit-based latency problems on the line. Operations Research Letters,2008,36:333-337.
[41]Y. Karuno, H. Nagamochi,2-approximation algorithms for the multi-vehicle schedul-ing problem on a path with release and handling times. Discrete Applied Mathemat-ics,2003,129:433-447.
[42]Y. Karuno, H. Nagamochi, An approximability result of the multi-vehicle schedul-ing problem on a path with release and handling times. Theoretical Computer Sci-ence,2004,312:267-280.
[43]I. Averbakh, O. Berman, A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree. Discrete Applied Mathematics,1996,68:17-32.
[44]I. Averbakh, O. Berman, (p-1)/(p+1)-approximate algorithm for p-traveling sales-men problems on a tree with minmax objective. Discrete Applied Mathemat-ics,1997,75:201-216.
[45]H. Nagamochi, K. Okada, A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree. Discrete Applied Mathematics,2004,140: 103-114.
[46]H. Nagamochi, K. Okada, Polynomial time 2-approximation algorithms for the min-max subtree cover problem. Lecture Notes in Computer Science,2003,2906:138-147.
[47]G.N. Frederickson, M.S. Hecht, C.E. Kim. Approximation algorithms for some rout-ing problems. SIAM Journal on Computing,1978,7(2):178-193.
[48]I. Averbakh, O. Berman, I. D. Chernykh, The routing open-shop problem on a network:complexity and approximation, Working Paper, The Rotman School of Management, University of Toronto,2002.
[49]I. Averbakh, O. Berman, I. D. Chernykh, A 6/5-approximation algorithm for the two-machine routing open-shop problem on a 2-node network. European Journal of Operational Research,2005,166:3-24.
[50]I. Averbakh, O. Berman, I. D. Chernykh, The routing open-shop problem on a network:Complexity and approximation. European Journal of Operational Re-search,2006,173:531-539.
[51]G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, M. Talamo, Algorithms for the on-line traveling salesman. Algorithmica,2001.29:560-581.
[52]M. Lipmann, On-line routing problems. PhD Thesis, Technische Universiteit Eind-hoven,2003.
[53]V. Bonifaci, Models and algorithms for online server routing. PhD thesis, Technische Universiteit Eindhoven,2007.
[54]P. Jaillet, M. R. Wagner, Online routing problems:value of advanced information as improved competitive ratios. Transportation Science,2006,40(2):200-210.
[55]G. Ausiello, M. Demange, L. Laura, V. Paschos, Algorithms for the on-line quota traveling salesman problem. Information Processing Letters.2004,92:89-94.
[56]N. Ascheuer, S.O. Krumke, J. Rambau. Online dial-a-ride problems:minimizing the completion time. In:H. Reichel and S. Tison, editors, Proc.17th Symp. on Theoretical Aspects of Computer Science, volume 1770 of Lecture Notes in Computer Science, pages 639-650, Springer-Verlag,2000.
[57]E. Feuerstein, L. Stougie, On-line single-server dial-a-ride problems. Theoretical Computer Science,2001,268:91-105.
[58]S.O. Krumke, W.E. de Paepe, D. Poensgen, L. Stougie, News from the online trav-eling repairman. Theoretical Computer Science,2003,295(1-3):279-294.
[59]C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization. Prentice Hall, Engle-wood Cliffs,1982.
[60]M.R. Garey, D.S. Johnson, Computers and Intractability:A Guide to the Theory of NP-completeness. Freeman, San Francisco,1979.
[61]B. Korte, J. Vygen, Combinatorial Optimization:Theory and Algorithms. Springer, 2007.
[62]P. Brucker, Scheduling Algorithms. Springer,1995.
[63]M. Pinedo, Scheduling:Theory, Algorithms, and Systems. Springer,2001.
[64]B. Chen, C.N. Potts, G.J. Woeginger, A review of machine scheduling:complexity, algorithms and approximability. In:D.-Z. Du, P.M. Pardalos (eds.), Handbook of Combinatorial Optimization, Vol.3, Kluwer Academic Publisher,1998,21-169.
[65]唐国春,张峰,罗守成,刘丽丽,现代排序论,上海科学普及出版社,2003.
[66]V.V. Vazirani, Approximation Algorithms. Springer,2001.
[67]G. Gutin, A.P. Punnen (eds.), The Traveling Salesman Problem and Its Variations. Kluwer Academic Publisher,2002.
[68]R. Bar-Yehuda, G. Even, S. Shahar, On approximating a geometric prize-collecting traveling salesman problem with time windows. Journal of Algorithms,2005.55: 76-92.
[69]F.A. Chudak, T. Roughgarden, D.P. Williamson, Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Mathematical Programming,2004,100:411-421.
[70]T. Gonzalez, S. Sahni, Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery,1976,23:665-679.
[71]俞文鱼此,刘朝晖.两台机器若干作业问题的双向排序法.华东理工大学学报.1999,25(6)：629-633.
[72]S.M. Johnson, Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly,1954,1:61-68.