The following on-line transportation problem (OLTP) is considered: Objects are to be transported between the vertices of a given graph. Transportation requests arrive on-line, specifying the objects to be transported and the corresponding source and target vertex. These requests are to be handled by a server which commences its work at a designated origin vertex and which picks up and drops objects at their starts and destinations. After the end of its service, the server returns to its start. The goal of OLTP is to come up with a transportation schedule for the server which finishes as early as possible. It is first shown that a lower bound of 5/3 exists for the competitive ratio of any deterministic algorithm. Two simple and natural strategies called Replan and Ignore are considered subsequently. Replan completely discards its schedule and recomputes a new one when a new request arrives. Ignore always runs a (locally optimal) schedule for a set of known request and ignores all new requests until this schedule is completed. Both strategies are shown to be 5/2-competitive. A somewhat less natural strategy Sleep is also presented which, in contrast to the other two strategies, may leave the server idle from time to time although unserved requests are known. Again, a competitive ratio of 5/2 is established for the algorithm Sleep. The results are extended to the case of 'open schedules' where the server is not required to return to its starting position at the end of its service.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen


    Exportieren, teilen und zitieren



    Titel :

    The online transportation problem: competitive scheduling of elevators


    Beteiligte:
    Ascheuer, N. (Autor:in) / Krumke, S.O. (Autor:in) / Rambau, J. (Autor:in)


    Erscheinungsdatum :

    1998


    Format / Umfang :

    11 Seiten, 1 Tabelle, 10 Quellen


    Medientyp :

    Report


    Format :

    Print


    Sprache :

    Englisch




    Elevators furnish safe transportation

    Bebb, J.C. | Engineering Index Backfile | 1930


    SYSTEM AND METHOD FOR SCHEDULING ELEVATORS

    APPANA AMANOS | Europäisches Patentamt | 2024

    Freier Zugriff

    SYSTEM AND METHOD FOR SCHEDULING ELEVATORS

    APPANA AMANOS | Europäisches Patentamt | 2022

    Freier Zugriff

    SYSTEM AND METHOD FOR SCHEDULING ELEVATORS

    AMARNAUTH APPANA JR | Europäisches Patentamt | 2022

    Freier Zugriff