Simon Emde

TY - JOUR

T1 - Optimally scheduling interfering and non-interfering cranes

AU - Emde, Simon

PY - 2017/9/1

Y1 - 2017/9/1

N2 - This article treats the problem of scheduling multiple cranes processing jobs along a line, where cranes are divided into different groups and only cranes in the same group can interfere with each other. Such crane scheduling problems occur, for example, at indented berths or in container yards where double rail-mounted gantry cranes stack containers such that cranes of the same size can interfere with each other but small cranes can pass underneath larger ones. We propose a novel algorithm based on Benders decomposition to solve this problem to optimality. In a computational study, it is shown that this algorithm solves small and medium-sized instances and even many large instances within a few seconds or minutes. Moreover, it improves several best known solutions from the literature with regard to the simpler problem version with only one crane group. We also look into whether investment in more complicated crane configurations with multiple crane groups is actually worthwhile.

AB - This article treats the problem of scheduling multiple cranes processing jobs along a line, where cranes are divided into different groups and only cranes in the same group can interfere with each other. Such crane scheduling problems occur, for example, at indented berths or in container yards where double rail-mounted gantry cranes stack containers such that cranes of the same size can interfere with each other but small cranes can pass underneath larger ones. We propose a novel algorithm based on Benders decomposition to solve this problem to optimality. In a computational study, it is shown that this algorithm solves small and medium-sized instances and even many large instances within a few seconds or minutes. Moreover, it improves several best known solutions from the literature with regard to the simpler problem version with only one crane group. We also look into whether investment in more complicated crane configurations with multiple crane groups is actually worthwhile.

KW - benders decomposition

KW - container logistics

KW - crane scheduling

KW - non-crossing constraints

UR - http://www.scopus.com/inward/record.url?scp=85034230631&partnerID=8YFLogxK

U2 - 10.1002/nav.21768

DO - 10.1002/nav.21768

M3 - Journal article

AN - SCOPUS:85034230631

VL - 64

SP - 476

EP - 489

JO - Naval Research Logistics

JF - Naval Research Logistics

SN - 0894-069X

IS - 6

ER -