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.


    Access

    Access via TIB

    Check availability in my library


    Export, share and cite



    Title :

    The online transportation problem: competitive scheduling of elevators


    Contributors:
    Ascheuer, N. (author) / Krumke, S.O. (author) / Rambau, J. (author)


    Publication date :

    1998


    Size :

    11 Seiten, 1 Tabelle, 10 Quellen


    Type of media :

    Report


    Type of material :

    Print


    Language :

    English




    Elevators furnish safe transportation

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


    SYSTEM AND METHOD FOR SCHEDULING ELEVATORS

    APPANA AMANOS | European Patent Office | 2024

    Free access

    SYSTEM AND METHOD FOR SCHEDULING ELEVATORS

    APPANA AMANOS | European Patent Office | 2022

    Free access

    Elevators

    Naylor, Charles W. | Engineering Index Backfile | 1917