线形网络上单台车辆分群调度问题

本文研究线形网络上单台车辆分群调度问题:若干客户分布在一条直线上,它们被划分成若干个连续子集,其中每个子集称为一个群;每个客户有一个释放时间和一个服务时间;一台机器服务所有客户,且要求每个群内的客户连续服务;目标为极小化时间表长。该问题分两种形式:返回型和不返回型。返回型的时间表长定义为机器服务完所有客户后返回其初始位置的时间;不返回型的时间表长则定义为所有客户的最大完工时间。我们的结果是:对每个客户服务时间为零的情形,证明了两种形式均可在O(n²) 时间内解决;对每个客户服务时间任意的情形,就返回型和不返回型,分别给出了16/9和13/7近似算法。

Single Vehicle Scheduling Problems with Cluster and Release Time Constraints on a Line

We consider the single vehicle scheduling problem in which some customers with release and service time requirements, are located at the vertices of a line, and a vehicle, initially waiting at some vertex, has to serve all the customers. The customers are partitioned into several consecutive clusters, and the customers in each cluster must be served consecutively. The objective is to minimize the makespan. In the tour-version the makespan means the time when the vehicle returns to its initial location after serving all customers. While in the path-version the makespan refers to the maximum completion time of all customers. In the case where the service time of each customer is zero, we show that both versions can be solved in O(n²)time. In the case where the service time of each customer is given arbitrarily, we present a 16/9-approximation algorithm for the tour-version and a 13/7-approximation algorithm for the path-version.