Vi studerar ett schemaläggningsproblem där jobb har platser. Tänk till exempel på en reparatör som förväntas besöka sina kunder i sina hem. Varje kund får ett tidsfönster under vilket reparatören tillåts anlända. Målet är att hitta ett schema som besöker så många hem som möjligt. Vi hänvisar till detta problem som Prize-Collecting Traveling Salesman Problem med tidsfönster (TW-TSP). Vi överväger två versioner av TW-TSP. I den första versionen finns jobb på en rad, har releasetider och deadlines men inga behandlingstider. Vi presenterar en geometrisk tolkning av TW-TSP på en linje som generaliserar det längsta monotona subsekvensproblemet. Vi presenterar en O(log n) approximationsalgoritm för detta fall, där n betecknar antalet jobb. Denna algoritm kan utvidgas för att hantera icke-enhetsarbetsvinster. Den andra versionen behandlar ett allmänt fall av asymmetriska avstånd mellan platser. Vi definierar en densitetsparameter som löst taget begränsar antalet sicksackar mellan platser inom ett tidsfönster. Vi presenterar en dynamisk programmeringsalgoritm som hittar en tur som besöker minst OP T / densitet platser under sin tid fönster. Denna algoritm kan utvidgas för att hantera icke-enhetsarbetsvinster och behandlingstider.
Om enhet-tid fönster, en (4 + )-uppskattning gavs för reparatören på en linje i REF.
On approximating a geometric prize-collecting traveling salesman problem with time windows
{'venue': 'Journal of Algorithms', 'journal': 'Journal of Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}