Search

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]