A m-Parallel Crane Scheduling Problem with a Non-Crossing Constraint
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.
modeling, machine scheduling, crane, approximation, heuristics, search
Operations and Supply Chain Management
Naval Research Logistics
LIM, Andrew; RODRIGUES, Brian; and XU, Zhou.
A m-Parallel Crane Scheduling Problem with a Non-Crossing Constraint. (2007). Naval Research Logistics. 54, (2), 115-127. Research Collection Lee Kong Chian School Of Business.
Available at: http://ink.library.smu.edu.sg/lkcsb_research/606