Scheduling with multiple-job-on-one-processor pattern

Chung Lun Li, Xiaoqiang Cai, Chung Yee Lee

Research output: Journal article publicationJournal articleAcademic researchpeer-review

102 Citations (Scopus)

Abstract

Most scheduling literature considers a “one-job-on-one-processor” pattern, which assumes that a processor processes exactly one job at a time. In this paper we consider a new scheduling problem with a “multiple-job-on-one-processor” pattern, where several jobs can be processed by a single processor simultaneously, provided that the total size of the jobs being processed does not exceed the capacity of the processor at any point in time. This problem is motivated by the operation of berth allocation, which is to allocate vessels (jobs) to a berth (processor), where the vessels, if small in dimension, may share the berth with some other vessels for loading/unloading the goods. We consider the problem to minimize the makespan of the schedule. The well-known First-Fit Decreasing heuristic is generalized and applied to several variations of the problem, and the worst-case behavior of the generalized heuristics is studied. Worst-case error bounds are obtained for those models. Computational experiments are conducted to test the heuristics. The results suggest that the heuristics are effective in producing near-optimal solutions.
Original languageEnglish
Pages (from-to)433-445
Number of pages13
JournalIIE Transactions (Institute of Industrial Engineers)
Volume30
Issue number5
DOIs
Publication statusPublished - 1 Jan 1998
Externally publishedYes

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Cite this