ДОСЛІДЖЕННЯ ЕФЕКТИВНОСТІ АЛГОРИТМУ ПОБУДОВИ ДОПУСТИМОГО РОЗКЛАДУ ДЛЯ ОДНОГО ПРИЛАДУ З РІЗНИМИ ДИРЕКТИВНИМИ ТЕРМІНАМИ ЗА КРИТЕРІЄМ МІНІМАЛЬНОГО СУМАРНОГО ВИПЕРЕДЖЕННЯ. (Ukrainian)

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
  • Additional Information
    • Alternate Title:
      EFFICIENCY RESEARCH OF ALGORITHM FOR A FEASIBLE SCHEDULE CONSTRUCTION BY THE TOTAL EARLINESS MINIMIZATION CRITERION ON SINGLE MACHINE WITH DIFFERENT DUE DATES. (English)
      ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА ПОСТРОЕНИЯ ДОПУСТИМОГО РАСПИСАНИЯ ДЛЯ ОДНОГО ПРИБОРА С РАЗЛИЧНЫМИ ДИРЕКТИВНЫМИ СРОКАМИ ПО КРИТЕРИЮ МИНИМАЛЬНОГО СУММАРНОГО ОПЕРЕЖЕНИЯ. (Russian)
    • Abstract:
      We research a scheduling algorithm for a feasible schedule construction on one machine by the total earliness of jobs minimization criterion. We propose an improvement to this algorithm. During the research, we have developed a software system to verify reliability of the algorithms. We compared the schedules built by the algorithm with those constructed by an exhaustive enumeration. We calculated the percentage of a non-exact schedule construction by the investigated algorithm for different characteristics of the schedule. The object of research is the process of schedules' optimization and their investigation. The purpose of the paper is to increase the efficiency of feasible schedules construction process for one machine in the presence of penalties for jobs completion prior to their due dates. We need to use appropriate economic and mathematical methods, in particular those from scheduling theory, to organize the production and planning on an enterprise efficiently. Scheduling problems have a great application value today. Rapid development of communication and electronics technologies increasingly requires the construction of schedules. The schedules are related to functioning of industrial enterprises and the service sector, education, transport and many other areas. Tasks of scheduling theory include study of the computational complexity of the problems and development of exact, approximation and heuristic algorithms for their solution. Most papers are devoted to combinatorial approaches' development. However, as practice shows, possibilities of combinatorial algorithms are substantially limited by the dimension of the problems they solve. This is why we believe in importance of the research and improvement of the scheduling algorithm to minimize the total earliness of jobs on one machine. We use combinatorial optimization methods, scheduling theory, heuristic algorithms and statistical analysis. The scientific novelty of the results consists in modification to the existing scheduling algorithm that minimizes the total earliness on one machine. New algorithm has better efficiency than the existing ones. [ABSTRACT FROM AUTHOR]
    • Abstract:
      В данной статье исследуется алгоритм составления допустимого расписания выполнения работ по критерию минимального опережения для задач на одном приборе в теории расписаний. Предложено усовершенствование данного алгоритма. В ходе исследований была разработана программная система для проверки достоверности работы алгоритмов. Сравниваются расписания, составленные алгоритмом и сформированные полным перебором. Для различных характеристик расписания подсчитано процентный фактор ошибки при составлении расписания исследуемым методом. Объект исследования – процесс оптимизации расписаний и их исследование. Цель работы – повышение эффективности процесса построения допустимых расписаний для одного прибора при наличии штрафов за окончание работы до директивного срока ее выполнения. Для эффективной организации производства и планирования работы предприятия необходимо использовать соответствующие экономико-математические методы, в частности, методы теории расписаний. В наше время задачи теории расписаний имеют большое прикладное значение. Быстрое развитие связи и техники все чаще вызывает необходимость построения расписаний, связанных с функционированием промышленных предприятий и сферы обслуживания, образованием, транспортом и многими другими областями. Проблематика теории расписаний охватывает исследования вычислительной сложности задач, разработку точных, приближенных и эвристических алгоритмов их решения. При этом большинство работ посвящено развитию комбинаторных подходов. Однако, как показывает практика, возможности комбинаторных алгоритмов существенно ограничены размерностью решаемых задач. В связи с этим актуальным является исследование и улучшение алгоритма составления расписания выполнения работ одним прибором с целью минимизации суммарного опережения. В исследовании используются методы комбинаторной оптимизации, теория расписаний, эвристические алгоритмы и статистический анализ. Научная новизна полученных результатов заключается в модификации существующего алгоритма построения расписания, минимизирующего суммарное опережение для одного прибора, и его лучшая эффективность по сравнению с существующими алгоритмами. [ABSTRACT FROM AUTHOR]
    • Abstract:
      Copyright of Informatics & Mathematical Methods in Simulation is the property of Odessa Polytechnic University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)