Scheduling problems of stationary objects with the processor in one-dimensional zone

N. A. Dunichkina ; D. I. Kogan ; Yu. S. Fedosenko

Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 3, pp. 356-371

Résumé

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 bi-criteria 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.

Détail

Keywords: scheduling, dynamic programming, $NP$-complexity, multicriteria optimization.
Mots-clés : Pareto concept