On the k-truck scheduling problem
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 + 0) (.) k/(o (.) k + 2) for the on-line k-truck problem is given, where theta 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/theta + 1/theta +1)-competitive algorithm for the on-line k-truck problem depending on the value of theta, 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)/theta)-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.
k-truck problem competitive ratio position maintaining strategy partial-greedy algorithm on-line algorithm