A note on scheduling container storage operations of two non‐passing stacking cranes. Issue 3 (20th December 2017)

• Record Type: Journal Article
• Authors: Kovalyov, Mikhail Y.; Pesch, Erwin; Ryzhikov, Andrew
• Is Part Of: Networks. Volume 71:Issue 3(2018)
• Page Start: 271
• Page End: 280
• Publication Date: 2017-12-20
• Subjects: algorithms -- approximation -- computational complexity -- logistics -- scheduling -- stacking cranes; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21803
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : We study a scheduling problem for a container block, in which there are incoming containers only. Container placement is served by two non‐passing stacking cranes based at the opposite sides of the container block. The same time is required for any crane to move between two adjacent bays of the container block and the same different time is required for any crane to perform any down‐and‐up operation related to container lifting at the pick‐up point or container lowering at the storage point. Containers are assigned to the cranes according to one of the following policies: (1) two fixed sequences policy where a container processing sequence is given for each crane, (2) dedicated crane policy where containers are preassigned to the cranes, (3) one fixed, one arbitrary sequence policy where a container processing sequence is given for one crane and it can be arbitrary for the other crane, (4) flexible policy where any container can be assigned to any crane at any time, and (5) global fixed sequence policy where the container sequence is given and the relative processing order of containers in this sequence must be preserved by any crane. The objective is to minimize the completion time of the latest operation. We show that the problem is polynomially solvable for policy 1 and, if the number of containers to be placed in the same bay is no more than a half of all containers, for policy 4. It is NP‐hard in the strong sense for policies 2 and 3. Approximation algorithms with guaranteed absolute and relative deviations from the optimum are devised for policies 4 and 5. The results translate for the case of outgoing containers only.