A m-Parallel Crane Scheduling Problem with a Non-Crossing Constraint

• Main Authors: LIM, Andrew, RODRIGUES, Brian, XU, Zhou
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2007
• Subjects: modeling; machine scheduling; crane; approximation; heuristics; search; Operations and Supply Chain Management
• Online Access: https://ink.library.smu.edu.sg/lkcsb_research/606; https://doi.org/10.1002/nav.20189
• Institution: Singapore Management University

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.