Computer-Aided Complexity Classification of Dial-a-Ride Problems

References

• Afrati F., Cosmadakis S., Papadimitriou C. H., Papageorgiou G., Papakonstantinou N. The complexity of the travelling repairman problem. Theoret. Informatics Appl. (1986) 20:79–87Crossref, Google Scholar
• Ascheuer N., Krumke S. O., Rambau J. Online dial-a-ride problems: Minimizing the completion time. Proc. 17th Internat. Sympos. on Theoret. Aspects of Comput. Sci., Lecture Notes in Computer Science (2000) (Springer, Berlin, Germany) 639–650No. 1770Crossref, Google Scholar
• Atallah M. J., Kosaraju S. R. Efficient solutions to some transportation problems with applications to minimizing robot arm travel. SIAM J. Comput. (1988) 17:849–870Crossref, Google Scholar
• Conway R. W., Maxwell W. L., Miller L. W.Theory of Scheduling (1967) (Addison-Wesley, Reading, MA) Google Scholar
• de Paepe W. E. Computer-aided complexity classification of dial-a-ride problems. (1998) . M.Sc. thesis, Department of Economics and Econometrics, University of Amsterdam, Amsterdam, The NetherlandsGoogle Scholar
• Desrochers M., Lenstra J. K., Savelsbergh M. W. P. A classification scheme for vehicle routing and scheduling problems. Eur. J. Oper. Res. (1990) 46:322–332Crossref, Google Scholar
• Feuerstein E., Stougie L. On-line single server dial-a-ride problems. Theoret. Comput. Sci. (2001) 268:91–105Crossref, Google Scholar
• Frederickson G. N., Guan D. J. Preemptive ensemble motion planning on a tree. SIAM J. Comput. (1992) 21:1130–1152Crossref, Google Scholar
• Frederickson G. N., Guan D. J. Non-preemptive ensemble motion planning on a tree. J. Algorithms (1993) 15:29–60Crossref, Google Scholar
• Frederickson G. N., Hecht M. S., Kim C. E. Approximation algorithms for some routing problems. SIAM J. Comput. (1978) 7:178–193Crossref, Google Scholar
• Garey M. R., Johnson D. S. Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput. (1975) 4:397–411Crossref, Google Scholar
• Garey M. R., Johnson D. S., Miller G. L., Papadimitriou C. H. The complexity of coloring circular arcs and chords. SIAM J. Algebraic Discrete Methods (1980) 1:216–227Crossref, Google Scholar
• Gonzalez T. Optimal mean finish time preemptive schedules. (1977) . Technical report 220, Computer Science Department, The Pennsylvania State University, University Park, PAGoogle Scholar
• Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. (1979) 5:287–326Crossref, Google Scholar
• Guan D. J. Routing a vehicle of capacity greater than one. Discrete Appl. Math. (1988) 81:41–57Crossref, Google Scholar
• Jackson J. R. Scheduling a production line to minimize maximum tardiness. (1955) . Research Report 43, Management Science Research Project, University of California, Los Angeles, CAGoogle Scholar
• Karp R. M., Miller R. E., Thatcher J. W. Reducibility among combinatorial problems. Complexity of Comput. Comput. (1972) (Plenum Press, New York) 85–103Crossref, Google Scholar
• Kendall D. G. Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain. Ann. Math. Statist. (1953) 24:338–354Crossref, Google Scholar
• Lageweg B. J., Lenstra J. K., Lawler E. L., Rinnooy Kan A. H. G. Computer-aided complexity classification of combinatorial problems. Comm. ACM (1982) 25:817–822Crossref, Google Scholar
• Lawler E. L., Moore J. M. A functional equation and its application to resource allocation and sequencing problems. Management Sci. (1969) 16:77–84Link, Google Scholar
• Lenstra J. K., Rinnooy Kan A. H. G. Complexity of vehicle routing and scheduling problems. Networks (1981) 11:221–227Crossref, Google Scholar
• Lenstra J. K., Rinnooy Kan A. H. G., Brucker P. Complexity of machine scheduling problems. Ann. Discrete Math. (1977) 1:343–362Crossref, Google Scholar
• Middendorf M. More on the complexity of common superstring and supersequence problems. Theoret. Comput. Sci. (1994) 125:205–228Crossref, Google Scholar
• Sitters R. A., Aardal K., Gerards B. Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines. Integer Programming Combin. Optim., Lecture Notes in Comput. Sci. (2001) (Springer, Berlin, Germany) 396–405No. 2081Crossref, Google Scholar
• Sitters R. A., Cook W. J., Schulz A. S. The minimum latency problem is NP-hard for weighted trees. Integer Programming Combin. Optim., Lecture Notes in Comput. Sci. (2002) (Springer, Berlin, Germany) 230–239No. 2337Crossref, Google Scholar
• Smith W. E. Various optimizers for single-stage production. Naval Res. Logist. Quart. (1956) 3:59–66Crossref, Google Scholar
• Tsitsiklis J. N. Special cases of traveling salesman and repairman problems with time windows. Networks (1992) 22:263–282Crossref, Google Scholar