AN EFFICIENT OPTIMAL SOLUTION OF A TWO-CRANE SCHEDULING PROBLEM

Weihua Zhou () and Xiaobo Wu
Additional contact information
Weihua Zhou: School of Management, Zhejiang University, P. R. China
Xiaobo Wu: School of Management, Zhejiang University, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2009, vol. 26, issue 01, 31-58

Abstract: This paper studies a two-crane scheduling problem in a port terminal. These two cranes are deployed in a block of a port terminal. They can move along a bi-directional traveling lane and must maintain a safe distance between them to avoid collision. A group of export containers in a block is required to be transported by cranes from their storage location to an access point of the block. Each container is associated with a due date. The problem is to find a schedule such that all containers are carried to the access point before their due dates. If such schedule does not exist, then the problem becomes to find schedules to minimize the maximum tardiness, the number of tardy jobs, respectively. In this paper, we first identify the necessary and sufficient conditions for the existence of a feasible schedule, i.e., a schedule transports all containers to the access point before their due dates and does not violate the requirement to maintain a safe distance between two cranes. We prove that if there exists at least one feasible schedule, then there must be a permutation schedule with containers sequenced in earliest due date (EDD) order to be feasible. An efficient algorithm is developed to find a feasible schedule given its existence. Furthermore, we provide efficient algorithms for minimizing the maximum tardiness, the number of tardy jobs, the makespan and the total completion time, respectively.

Keywords: Crane; scheduling; non-crossing constraint; optimization (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595909002146
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:26:y:2009:i:01:n:s0217595909002146

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595909002146

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().