A two-stage scheduling problem arising from locomotive dispatching in mine railway

• Autorzy: Lin X. , Wang X.
• Języki publikacji: EN

Abstrakty

EN

A locomotive dispatching problem arose from a coal mining area in 1950's: 2n jobs are executed by a locomotive, where n preceding jobs J,: with deadlines di (1≤ i ≤ n] represent sending empty cars to n pits from the central station, while n successive jobs Jt- with release dates r( (1≤ i ≤ n] represent drawing back the loaded cars from n pits to the station; in order to reduce the detaining and increase the turnover rate of freight cars, we are asked to find a schedule of the locomotive so that the maximum flow-time is minimized. Here, the flow-time of a job is the difference between the deadline and the starting time (for a preceding job) or between the completion time and the release date (for a successive job). The present paper studies this two-stage single machine scheduling problem. The main result is a polynomial algorithm for solving it. Meanwhile, two variant models are discussed, one is easier and one is harder. The algorithms here can be regarded as generalizations of the EDD-ERD rule.

Słowa kluczowe

EN

scheduling problem; locomotive dispatching; algorithm; complexity

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2007
• Tom: Vol. 32, No. 2
• Strony: 125--137
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Lin X.

autor

Wang X.

• Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, China,

Bibliografia

• [1] Agnetis A., Mirchandani P.B., Pacciarelli D., Pacific! A., Scheduling problems with two competing agents. Operations Research, 52, 2004. 229-242.
• [2] Bondy J.A., Murty U.S.R., Graph Theory with Applications, The Macmillan Press Ltd. London, 1976.
• [3] Brucker P., Scheduling Algorithms, Springer-Verlag, Berlin. 2001.
• [4] Brucker P.. Knust S.. Complexity results for single-machine problems with positive finish-start time-lags, Computing, 63, 1999, 299-316.
• [5] Garey M.R.. Johnson D.S., Computers and intractability: A guide to the theory of NP-completcness, W.H. Freeman arid Company, San Francisco, 1979.
• [6] Gupta J.X.D.. Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags, Journal of Global Optimization, 9, 1996, 239-253.
• [7] Hall K.G., Potts C.N.. Rescheduling for new orders. Operations Research. 52, 2004, 440-453.
• [8] Lawler E.L., Combinatorial Optimization: Networks and Matroids, Holt, Rine-hart &: Winston, Xew York, 1976.
• [9] Lin Y., Applications of Scheduling theory to the locomotive dispatching problem, Journal of Zheugzhou University, 2, 1987, 1-8 (in Chinese).
• [10] Pinedo M.. Scheduling: Theory. Algorithms, and Systems. Prentice-Hall. Engle-wood Cliffs, NJ, 1995.
• [11] Zhang W.. A problem of locomotive dispatching in mine railway. Journal of Zhengzhou University, 1, 1981, 44-54 (in Chinese).