Optimal servicing strategy design problems for stationary objects in a one-dimensional working zone of a processor. (English. Russian original) Zbl 1203.93128
Autom. Remote Control 71, No. 10, 2058-2069 (2010); translation from Avtom. Telemekh. 2010, No. 10, 50-62 (2010).
Summary: We introduce a model of one-stage service for a group of stationary objects located along a one-dimensional working zone of a moving processor. For servicing, the processor sequentially performs two passes between boundary points of the working zone: the direct pass, servicing some of the objects, and the reverse pass, servicing all remaining objects of a group. With each object, we associate an individual penalty function that increases monotone with the time of finishing its servicing. We formulate design problems for optimal servicing strategies, give algorithms of their solutions, and study the issues of computational complexity.
MSC:
| 93C83 | Control/observation systems involving computers (process control, etc.) |
| 68M07 | Mathematical problems of computer architecture |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 49N90 | Applications of optimal control and differential games |
References:
| [1] | Tanaev, V.S., Gordon, V.S., and Shafransky, Ya.M., Teoriya raspisanii. Odnostadiinye sistemy (Scheduling Theory. Single-stage Systems), Moscow: Nauka, 1984. |
| [2] | Tanaev, V.S., Sotskov, Yu.N., and Strusevich, V.A., Teoriya raspisanii. Mnogostadiinye sistemy (Scheduling Theory. Multi-stage Systems), Moscow: Nauka, 1989. |
| [3] | Tanaev, V.S., Kovalyov, M.Ya., and Shafransky, Ya.M., Teoriya raspisanii. Gruppovye tekhnologii (Scheduling theory. Group technologies), Minsk: ITK, 1998. |
| [4] | Brucker, P. and Knust, S., Complex Scheduling, New York: Springer, 2006. |
| [5] | Pinedo, M., Scheduling. Theory, Algorithms and Systems, New York: Springer, 2008. · Zbl 1155.90008 |
| [6] | Kogan, D.I., Fedosenko, Yu.S., and Shlyugaev, A.Yu., The Problem of Single-stage Servicing of Extracting Complexes in a Large-scale Water Basin, in Tr. V Mosk. mezhdunar. konf. po issledovaniyu operatsii (Proc. V Moscow International Conference on Operations Research (ORM2007)), Moscow: MAKS Press, 2007, pp. 60–62. |
| [7] | Kogan, D.I., Fedosenko, Yu.S., and Shlyugaev, A.Yu., A Mathematical Model and a Synthesis Algorithm for Suboptimal Schedules for Single-processor Servicing of a Spatially Distributed Group of Stationary Objects, in Tr. VI mezhdunar. konf. ”Identifikatsiya sistem i zadachi upravleniya” (Proc. of the VI International conference ”System identification and control problems”), Moscow: Inst. Probl. Upravlen., 2007, pp. 1026–1038. |
| [8] | Shen, H., Optimal Scheduling for Satellite Refueling in Circular Orbits, PhD Dissertation, Atlanta: School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, Georgia, 2003. |
| [9] | Shen, H. and Tsiotras, P., Peer-to-Peer Refueling for Circular Satellite Constellations, AIAA J. Guidance. Control Dynam., 2005, vol. 28, no. 6, pp. 1220–1230. · doi:10.2514/1.9570 |
| [10] | Kogan, D.I. and Fedosenko, A.Yu., The Discretization Problem: Analysis of Computational Complexity, and Polynomially Solvable Subclasses, Discrete Math. Appl., 1996, vol. 6, no. 5, pp. 435–447. · Zbl 0869.90038 · doi:10.1515/dma.1996.6.5.435 |
| [11] | Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NPCompleteness, San Francisco: Freeman, 1979. Translation under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Moscow: Mir, 1982. |
| [12] | Bellman, R.E. and Dreyfus, S.E., Applied Dynamic Programming, Prinston: Princeton Univ. Press, 1962. Translated under the title Prikladnye zadachi dinamicheskogo programmirovaniya, Moscow: Mauka, 1965. · Zbl 0106.34901 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
