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

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.