Improved algorithms for two single machine scheduling problems
Improved algorithms for two single machine scheduling problems
复制标题
DOI：
10.1016/j.tcs.2006.04.014
复制
发表时间：
2005-06
期刊：
影响因子：
--
通讯作者：
Yong He;Weiya Zhong;Huikun Gu
中科院分区：
文献类型：
--
作者：
Yong He;Weiya Zhong;Huikun Gu
本文研究了两个单机排序问题。第一个问题解决了一类两阶段调度问题，其中第一阶段是工件生产，第二阶段是工件交付。对于工件在单个机器上处理并由单个车辆运送到一个客户区域的情况，以最小化所有工件完成并运送到客户区域以及车辆返回机器的时间为目标，已知具有最坏情况比53的近似算法，并且除非P=NP，否则没有近似可以具有最坏情况32。我们提出了一种改进的近似算法，最坏情况下的比率为5335，只留下170的差距。第二个问题是带维修期的单机排序问题。目标是最小化总完工时间。最知名的近似算法的最差情况比率为2017。我们提出了一个多项式时间近似方案。
In this paper, we investigate two single machine scheduling problems. The first problem addresses a class of the two-stage scheduling problems in which the first stage is job production and the second stage is job delivery. For the case that jobs are processed on a single machine and delivered by a single vehicle to one customer area, with the objective of minimizing the time when all jobs are completed and delivered to the customer area and the vehicle returns to the machine, an approximation algorithm with a worst-case ratio of 53 is known and no approximation can have a worst-case of 32 unless P=NP. We present an improved approximation algorithm with a worst-case ratio of 5335, which only leaves a gap of 170. The second problem is a single machine scheduling problem subject to a period of maintenance. The objective is to minimize the total completion time. The best known approximation algorithm has a worst-case ratio of 2017. We present a polynomial time approximation scheme.