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

Andrew Lim, Brian Rodrigues, Zhou Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

98 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)115-127
Number of pages13
JournalNaval Research Logistics
Issue number2
Publication statusPublished - 1 Mar 2007
Externally publishedYes


  • Approximation
  • Crane
  • Heuristics
  • Machine scheduling
  • Modeling
  • Search

ASJC Scopus subject areas

  • Management Science and Operations Research

Cite this