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.
Original language | English |
---|---|
Pages (from-to) | 115-127 |
Number of pages | 13 |
Journal | Naval Research Logistics |
Volume | 54 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Mar 2007 |
Externally published | Yes |
Keywords
- Approximation
- Crane
- Heuristics
- Machine scheduling
- Modeling
- Search
ASJC Scopus subject areas
- Management Science and Operations Research