TOTAL WEIGHTED TARDINESS MINIMIZATION FOR TASKS WITH A COMMON DUE DATE ON PARALLEL MACHINES IN CASE OF AGREEABLE WEIGHTS AND PROCESSING TIMES
Journal Title: Вісник Національного технічного університету «ХПІ». Серія: Системний аналiз, управління та iнформацiйнi технологiї - Year 2019, Vol 0, Issue 1
Abstract
We consider tasks scheduling problem on identical parallel machines by the criterion of minimizing the total weighted tardiness of tasks. All tasks arrive for processing at the same time. Weights and processing times are agreeable, that is, a greater weight of a task corresponds to a shorter processing time. In addition, we have arbitrary start times of machines for tasks processing. The times may be less or greater than the due date or to coincide with it. The problem in this formulation is addressed for the first time. It can be used to provide planning and decision making in systems with a network representation of technological processes and limited resources. We give efficient PSC-algorithm with complexity that includes the polynomial component and the approximation algorithm based on permutations of tasks. The polynomial component contains sufficient signs of optimality of the obtained solutions and allows to obtain an exact solution by polynomial subalgorithm. In the case when the sufficient signs of optimality do not fulfill, we obtain approximate solution with an estimate of deviation from the optimum for each individual problem instance of any practical dimension. We show that a schedule obtained as a result of the problem solving can be split into two schedules: the schedule on machines which start time is less than or equal to the due date, and the schedule on machines which start after the due date. Optimization is only done in the first schedule. The second schedule is optimal by construction. Statistical studies of the PSC-algorithm showed its high efficiency. We solved problems with dimensions up to 40,000 tasks and up to 30 machines. The average time to solve the problem by the algorithm using the most efficient types of permutations was 27.3 ms for this dimension. The average frequency of an optimal solution obtaining amounted to 90.3 %. The average deviation from an optimum was no more than 0.000251.
Authors and Affiliations
Alexander Pavlov, Elena Misura, Oleg Melnikov
Keywords
Related Articles
- EP ID EP603775
- DOI 10.20998/2079-0023.2019.01.04
- Views 59
- Downloads 0
Medium-term planning information technology for quality improvement of the software development process based on the CMMI model
<p class="304">Information technology is considered for medium-term planning for quality improvement of the software development process based on the CMMI model for the dynamic problem statement. The information system f...
КОМП’ЮТЕРНЕ МОДЕЛЮВАННЯ ПРОЦЕСІВ ДИФУЗІЇ У ПОХИЛИХ ПРОСТОРОВО-ПЕРІОДИЧНИХ ПОТЕНЦІАЛАХ
Нещодавно було показано, що в істотно нерівноважних системах коефіцієнт дифузії може вести себе немонотонно з температурою. Одним із прикладів таких систем з аномальною температурної залежністю є рух броунівських часток...
DEVELOPMENT OF A DATABASE STRUCTURE FOR STORING MODELS FOR DETERMINATED ALPHABETES CLASSES RECOGNITION BASED ON THE SET OF HETEROGENEOUS CHARACTERISTIC
<p class="304Annotationeng">The objects and situations recognition is important problem in such areas as the definition of the types of air objects according to various sources of information, diagnosis of patients on th...
Имитационное моделирование процессов в реакторе ВВЭР-1000 при регулировании мощности поглощающими стержнями
<span>Представлены математические модели реактора ВВЭР-1000 серии В-320 в относительных переменных состояния, которые описывают нейтронную кинетику реактора, тепловые процессы, изменение концентрации ксенона при регулиро...
INFORMATION SUPPORT FOR THE ANALYSIS OF SKILLS AND ABILITIES OF UNIVERSITY STUDENTS
In the below article, the application of the fuzzy logical conclusion method is considered as decision-maker in the process of analyzing the students skills and abilities based on the requirements of potential employers,...