An instance of a p-median problem gives n demand points. The objective is to locate p supply points in order to minimize the total distance of the demand points to their nearest supply point. P-median is polynomially solvable in one dimension but NP-hard in two or more dimensions, when either the Euclidean or the rectilinear distance measure is used. In this thesis, we treat the p-median problem under a new distance measure, the directional rectilinear distance, which requires the nearest supply point for a given demand point to lie above and to the right of it. This restriction has applications to multiprocessor scheduling of periodic tasks as well as to traffic quantization and Quality of Service scheduling in packet-switched computer networks. We show that the directional p-median problem is polynomially solvable in one dimension and give two algorithms. We prove the problem NP-hard in two or more dimensions and then present an efficient heuristic to solve it. Compared to the robust Teitz and Bart heuristic for p-median, our heuristic enjoys substantial speedup while sacrificing little in terms of solution quality, making it an ideal choice for our target applications with thousands of demand points.
| Identifer | oai:union.ndltd.org:NCSU/oai:NCSU:etd-11052003-111956 |
| Date | 20 November 2003 |
| Creators | Jackson, Laura Elizabeth |
| Contributors | George N. Rouskas, Jeffrey Joines, Carla Savage, Matthias F.M. Stallmann |
| Publisher | NCSU |
| Source Sets | North Carolina State University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://www.lib.ncsu.edu/theses/available/etd-11052003-111956/ |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to NC State University or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.0016 seconds