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

Chinese Journal of Management Science ›› 2005, Vol. ›› Issue (4): 44-50.

Previous Articles Next Articles

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

CLC Number:

F830

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.

References

[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.

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

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Metrics

Comments

Recommended 0