On the k-truck scheduling problem

Weimin Ma, Yinfeng Xu, Jia You, James Liu, Kanliang Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

In this paper, some results concerning the k-truck problem are produced. Firstly, the algorithms and their complexity concerning the off-line k-truck problem are discussed. Following that, a lower bound of competitive ratio (1+θ)·k/(θ·k+2) for the on-line k-truck problem is given, where θ is the ratio of cost of the loaded truck and the empty truck on the same distance, and a relevant lower bound for the on-line k-taxi problem followed naturally. Thirdly, based on the Position Maintaining Strategy (PMS), some new results which are slightly better than those of [11] for general cases are obtained. For example, a c-competitive or (c/θ+1/θ+1)- competitive algorithm for the on-line k-truck problem depending on the value of θ, where c is the competitive ratio of some algorithm to a relevant k-server problem, is developed. The Partial-Greedy Algorithm (PG) is used as well to solve this problem on a line with n nodes and is proved to be a (1+(n-k)/θ)-competitive algorithm for this case. Finally, the concepts of the on-line k-truck problem are extended to obtain a new variant: Deeper On-line k-Truck Problem (DTP). We claim that results of PMS for the STP (Standard Truck Problem) hold for the DTP.
Original languageEnglish
Pages (from-to)127-141
Number of pages15
JournalInternational Journal of Foundations of Computer Science
Volume15
Issue number1
DOIs
Publication statusPublished - 1 Dec 2004

Keywords

  • Competitive ratio
  • K-Truck problem
  • On-line algorithm
  • Partial-Greedy Algorithm
  • Position Maintaining Strategy

ASJC Scopus subject areas

  • Computer Science (miscellaneous)

Cite this