A multiprocessor task scheduling model for berth allocation: Heuristic and worst-case analysis

Yongpei Guan, Wen Qiang Xiao, Raymond K. Cheung, Chung Lun Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

117 Citations (Scopus)

Abstract

We consider a scheduling problem in which the processors are arranged along a straight line, and each job requires simultaneous processing by multiple consecutive processors. We assume that the job sizes and processing times are agreeable. Our objective is to minimize the total weighted completion time of the jobs. This problem is motivated by the operation of berth allocation, which is to allocate vessels (jobs) to a berth with multiple quay cranes (processors), where a vessel may be processed by multiple consecutive cranes simultaneously. We develop a heuristic for the problem and perform worst-case analysis.
Original languageEnglish
Pages (from-to)343-350
Number of pages8
JournalOperations Research Letters
Volume30
Issue number5
DOIs
Publication statusPublished - 1 Oct 2002
Externally publishedYes

Keywords

  • Heuristic
  • Scheduling
  • Sequencing

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Cite this