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

Publication Type

Journal Article

Publication Date

3-2007

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.

Keywords

modeling, machine scheduling, crane, approximation, heuristics, search

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

Naval Research Logistics

Volume

54

Issue

2

First Page

115

Last Page

127

ISSN

0894-069X

Identifier

10.1002/nav.20189

Publisher

Wiley

Additional URL

https://doi.org/10.1002/nav.20189

Link to Full Text

Share

COinS