SCHEDULING PROBLEMS OF STATIONARY OBJECTS WITH THE PROCESSOR IN ONE-DIMENSIONAL ZONE
We consider the mathematical model in which an operating processor serves the set of the stationary objects positioned in a one-dimensional working zone. The processor performs two voyages between the uttermost points of the zone: the forward or direct one, where certain objects are served, and the...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2015-06-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/256 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849338766600175616 |
|---|---|
| author | N. A. Dunichkina D. I. Kogan Yu. S. Fedosenko |
| author_facet | N. A. Dunichkina D. I. Kogan Yu. S. Fedosenko |
| author_sort | N. A. Dunichkina |
| collection | DOAJ |
| description | We consider the mathematical model in which an operating processor serves the set of the stationary objects positioned in a one-dimensional working zone. The processor performs two voyages between the uttermost points of the zone: the forward or direct one, where certain objects are served, and the return one, where remaining objects are served. Servicing of the object cannot start earlier than its ready date. The individual penalty function is assigned to every object, the function depending on the servicing completion time. Minimized criteria of schedule quality are assumed to be total service duration and total penalty. We formulate and study optimization problems with one and two criteria. Proposed algorithms are based on dynamic programming and Pareto principle, the implementations of these algorithms are demonstrated on numerical examples. We show that the algorithm for the problem of processing time minimization is polynomial, and that the problem of total penalty minimization is NP-hard. Correspondingly, the bicriteria problem with the mentioned evaluation criteria is fundamentally intractable, computational complexity of the schedule structure algorithm is exponential. The model describes the fuel supply processes to the diesel-electrical dredgers which extract non-metallic building materials (sand, gravel) in large-scale areas of inland waterways. Similar models and optimization problems are important, for example, in applications like the control of satellite group refueling and regular civil aircraft refueling.The article is published in the author’s wording. |
| format | Article |
| id | doaj-art-5a522b31249646c8938dc9da1dc1ca7f |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2015-06-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-5a522b31249646c8938dc9da1dc1ca7f2025-08-20T03:44:18ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172015-06-0122335637110.18255/1818-1015-2015-3-356-371245SCHEDULING PROBLEMS OF STATIONARY OBJECTS WITH THE PROCESSOR IN ONE-DIMENSIONAL ZONEN. A. Dunichkina0D. I. Kogan1Yu. S. Fedosenko2Volga State University of Water Transport, Nizhny NovgorodMoscow State University of Instrument Engineering and InformaticsVolga State University of Water Transport, Nizhny NovgorodWe consider the mathematical model in which an operating processor serves the set of the stationary objects positioned in a one-dimensional working zone. The processor performs two voyages between the uttermost points of the zone: the forward or direct one, where certain objects are served, and the return one, where remaining objects are served. Servicing of the object cannot start earlier than its ready date. The individual penalty function is assigned to every object, the function depending on the servicing completion time. Minimized criteria of schedule quality are assumed to be total service duration and total penalty. We formulate and study optimization problems with one and two criteria. Proposed algorithms are based on dynamic programming and Pareto principle, the implementations of these algorithms are demonstrated on numerical examples. We show that the algorithm for the problem of processing time minimization is polynomial, and that the problem of total penalty minimization is NP-hard. Correspondingly, the bicriteria problem with the mentioned evaluation criteria is fundamentally intractable, computational complexity of the schedule structure algorithm is exponential. The model describes the fuel supply processes to the diesel-electrical dredgers which extract non-metallic building materials (sand, gravel) in large-scale areas of inland waterways. Similar models and optimization problems are important, for example, in applications like the control of satellite group refueling and regular civil aircraft refueling.The article is published in the author’s wording.https://www.mais-journal.ru/jour/article/view/256schedulingdynamic programmingpareto conceptnp-complexitymulticriteria optimization |
| spellingShingle | N. A. Dunichkina D. I. Kogan Yu. S. Fedosenko SCHEDULING PROBLEMS OF STATIONARY OBJECTS WITH THE PROCESSOR IN ONE-DIMENSIONAL ZONE Моделирование и анализ информационных систем scheduling dynamic programming pareto concept np-complexity multicriteria optimization |
| title | SCHEDULING PROBLEMS OF STATIONARY OBJECTS WITH THE PROCESSOR IN ONE-DIMENSIONAL ZONE |
| title_full | SCHEDULING PROBLEMS OF STATIONARY OBJECTS WITH THE PROCESSOR IN ONE-DIMENSIONAL ZONE |
| title_fullStr | SCHEDULING PROBLEMS OF STATIONARY OBJECTS WITH THE PROCESSOR IN ONE-DIMENSIONAL ZONE |
| title_full_unstemmed | SCHEDULING PROBLEMS OF STATIONARY OBJECTS WITH THE PROCESSOR IN ONE-DIMENSIONAL ZONE |
| title_short | SCHEDULING PROBLEMS OF STATIONARY OBJECTS WITH THE PROCESSOR IN ONE-DIMENSIONAL ZONE |
| title_sort | scheduling problems of stationary objects with the processor in one dimensional zone |
| topic | scheduling dynamic programming pareto concept np-complexity multicriteria optimization |
| url | https://www.mais-journal.ru/jour/article/view/256 |
| work_keys_str_mv | AT nadunichkina schedulingproblemsofstationaryobjectswiththeprocessorinonedimensionalzone AT dikogan schedulingproblemsofstationaryobjectswiththeprocessorinonedimensionalzone AT yusfedosenko schedulingproblemsofstationaryobjectswiththeprocessorinonedimensionalzone |