An m-parallel crane scheduling problem with a non-crossing constraint

An m-parallel crane scheduling problem with a non-crossing constraint

0.00 Avg rating0 Votes
Article ID: iaor20081910
Country: United States
Volume: 54
Issue: 2
Start Page Number: 115
End Page Number: 127
Publication Date: Mar 2007
Journal: Naval Research Logistics
Authors: , ,
Keywords: scheduling, search, vehicle routing & scheduling
Abstract:

In this paper, we study a m-parallel machine scheduling problem with a non-crossing constraint motivated by crane scheduling in ports. We decompose the problem to allow time allocations to be determined once crane assignments are known and construct a backtracking search scheme that manipulates domain reduction and pruning strategies. Simple approximation heuristics are developed, one of which guarantees solutions to be at most two times the optimum. For large-scale problems, a simulated annealing heuristic that uses random neighborhood generation is provided. Computational experiments are conducted to test the algorithms.

Reviews

Required fields are marked *. Your email address will not be published.