Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Quay crane allocation as a moldable task scheduling problem

SpeakerJacek Blazewicz

Co-authorsM. Machowiak and C. Oguz

In this paper, the allocation problem of berths to the incoming ships is modelled by a moldable tasks scheduling problem. This model considers the tasks as the ships and the processors as quay cranes assigned to these ships. Since the duration of berthing for a ship depends on the number of quay cranes allocated to the ship, the use of moldable task scheduling model is substantiated. In the model, the processing speed of a task is considered to be a non-linear function of the number of processors allocated to it. A suboptimal algorithm, which starts from the continuous version of the problem (i.e. where the tasks may require a fractional part of the resources) to obtain a feasible solution to the discrete version of the problem, is presented. The computational experiments conducted showed that the suboptimal algorithm has a very good average behavior.