Abstract
Latency problems are characterized by their focus on minimizing total waiting time for all clients. We consider periodic latency problems: an extension of standard latency problems. In a periodic latency problem each client has to be visited regularly. More precisely, given is a server traveling at unit speed, and a set of clients with their positions. To each client a periodicity is associated that is the maximal amount of time that is allowed to pass between consecutive visits of the server to that client. In a problem we denote as PLPP, the goal is then to find a repeatable route for the server visiting as many clients as possible without violating the periodicities. Further, we consider the PLP in which the number of servers needed to serve all clients is minimized. We give polynomial-time algorithms and NP-hardness results for these problems depending upon the topology of the underlying network.
Original language | English |
---|---|
Title of host publication | Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management (IEEM'09, Hong Kong, December 8-11, 2009) |
Publisher | Institute of Electrical and Electronics Engineers |
Pages | 296-300 |
ISBN (Print) | 978-1-4244-4869-2 |
DOIs | |
Publication status | Published - 2009 |
Event | 2009 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2009 - Hong Kong, Hong Kong Duration: 8 Dec 2009 → 11 Dec 2009 |
Conference
Conference | 2009 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2009 |
---|---|
Abbreviated title | IEEM 2009 |
Country/Territory | Hong Kong |
City | Hong Kong |
Period | 8/12/09 → 11/12/09 |