×

zbMATH — the first resource for mathematics

A multiprocessor task scheduling model for berth allocation: Heuristic and worst-case analysis. (English) Zbl 1010.90026
Summary: 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.

MSC:
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
65Y20 Complexity and performance of numerical algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brown, G.G.; Cormican, K.J.; Lawphongpanich, S.; Widdis, D.B., Optimizing submarine berthing with a persistence incentive, Naval res. logist., 44, 301-318, (1997) · Zbl 0889.90106
[2] C.-Y. Chen, T.-W. Hsieh, A time-space network model for the berth allocation problem, First International Conference of Maritime Engineering and Ports, Genoa, Italy, September 28-30, 1998.
[3] Chen, J.; Lee, C.-Y., General multiprocessor task scheduling, Naval res. logist., 46, 57-74, (1999) · Zbl 0922.90085
[4] Daganzo, C., The crane scheduling problem, Transportation res. B, 23B, 159-175, (1989)
[5] Drozdowski, M., Scheduling multiprocessor tasks—an overview, European J. oper. res., 94, 215-230, (1996) · Zbl 0949.68506
[6] S.P. Fekete, E. Köhler, J. Teich, Higher-dimensional packing with order constraints, Proceedings of the 7th International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 2125, Springer, Berlin, 2001, pp. 300-312. · Zbl 1018.90035
[7] Hadjiconstantinou, E.; Christofides, N., An exact algorithm for general, orthogonal, two-dimensional knapsack problems, European J. oper. res., 83, 39-56, (1995) · Zbl 0903.90124
[8] Lai, K.K.; Shih, K., A study of container berth allocation, J. adv. transportation, 26, 45-60, (1992)
[9] Lee, C.-Y.; Cai, X., Scheduling one and two-processor tasks on two parallel processors, IIE trans., 31, 445-455, (1999)
[10] Lee, C.-Y.; Lei, L.; Pinedo, M., Current trends in deterministic scheduling, Ann. oper. res., 70, 1-41, (1997) · Zbl 0890.90102
[11] Li, C.-L.; Cai, X.; Lee, C.-Y., Scheduling with multiple-job-on-one-processor pattern, IIE trans., 30, 433-445, (1998)
[12] Lim, A., The berth planning problem, Oper. res. lett., 22, 105-110, (1998) · Zbl 0911.90283
[13] Pinedo, M., Scheduling: theory, algorithms, and systems, (2002), Prentice-Hall Upper Saddle River, NJ · Zbl 1145.90394
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.