单资源调度中误工问题的作业时间压缩算法

中国管理科学 ›› 2005, Vol. ›› Issue (4): 44-50.

单资源调度中误工问题的作业时间压缩算法

彭敏¹, 杨丽², 许保光¹

1. 中国科学院科技政策与管理科学研究所, 北京, 100080;
2. 中国科学院研究生院, 北京, 100039

收稿日期:2005-02-16 修回日期:2005-06-20 出版日期:2005-08-28 发布日期:2012-03-07
基金资助:
国家自然科学基金资助项目(70371059)

An Algorithm for Delays Problems in Single Resource Scheduling with Compressible Processing Time

PENG Min¹, YANG Li², XU Bao-guang¹

1. Institute of Policy and Management, Chinese Academy of Sciences, Beijing 100080, China;
2. Graduate School Chinese Academy of Sciences, Beijing 100039, China

Received:2005-02-16 Revised:2005-06-20 Online:2005-08-28 Published:2012-03-07

摘要/Abstract

摘要： 本文采用作业时间可压缩的方法来解决单资源调度中的误工问题。在安排任务处理顺序的过程中,当某个任务发生误工时,我们基于关键路径反向搜索的方法,给出了一个启发式算法,求得需要压缩的任务集,使这个误工任务的延误时间尽可能的减少,并使需要压缩的任务数目最少,最后证明了算法的有效性,并给出了一个算例。

关键词: 压缩作业时间, 单资源调度, 误工, 关键工序

Abstract: In this paper,we consider the delays problems in single resource scheduling with compressible processing time.A heuristic algorithm is provided on the basis of reverse critical path and a set of tasks needing compression is picked up,when a delay task occurs in the process of scheduling tasks,with the objective of minimum length of delay time,and minimum number of compressed tasks.At the end,the validity of the heuristic is proved and an experimental result is showed.

Key words: compressible processing time, single resource scheduling, delays, critical procedure

中图分类号:

F830

彭敏, 杨丽, 许保光. 单资源调度中误工问题的作业时间压缩算法[J]. 中国管理科学, 2005, (4): 44-50.

PENG Min, YANG Li, XU Bao-guang. An Algorithm for Delays Problems in Single Resource Scheduling with Compressible Processing Time[J]. Chinese Journal of Management Science, 2005, (4): 44-50.

参考文献

[1] Lawler, E. L. and J. M. Moore. A functional equation and its application to resource allocation and sequencing problem[J].Man. Sci., 1969,16:77-84.
[2] R.G.Vickson. Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine[J]. Operation Research, 1980,28:1155-1167.
[3] R.G. Vickson. Two single machine sequencing problems involving controllable job processing times [J]. AIIE Trans,1980,12:258-262.
[4] A. Janiak, M. Y. Kovalyov. Single machine schedulings ubject to deadlines and resource dependent processing times[J]. European Journal of Operational Research, 1996, 94:284-291.
[5] R. L. Daniels,J. B. Mazzola. Flow shop scheduling with resource flexibility [J]. Operation Research, 1994,42: 504-522.
[6] J. Turek, J. Wolf, and P. Yu. Approximate algorithms for scheduling parallelizable tasks [C]. In 4th Annual ACM Symposium on Parallel Algorithms and Architectures,1992, 323-332.
[7] W. Ludwig, P. Tiwari, Scheduling malleable and nonmalleable parallel tasks[C]. In proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 1994,167-176.
[8] G. Mouni_ e, C. Rapine, D. Trystram. Effcient Approximation Algorithms for Scheduling Malleable Tasks [C]. In Proceedings of the Eleventh ACM Symposium on Parallel Algorithms and Architectures, 1999,23-32.
[9] 唐国春.可控排序和赶工排序.运筹学杂志,1994,13:1-4.
[10] 张峰.延误工件个数与最大加工时间压缩比例之和的可控排序.高校应用数学学报A辑,2004,19(2):241-245.
[11] Z.-L. Chen, Q. Lu, G, Tang. Single machine scheduling with discretely controllable processing times[J]. Operations Research Letters, 1997,21: 69-76.
[12] Oh-Heum Kwon, Kyung-Yong Chwa. Scheduling parallel tasks with individual deadlines [J]. Theoretical Computer Science, 1999,215:209-223.