Thesis for a candidate's technical science degree majoring in 05.13.06 - information technologies. - National Technical University of Ukraine "Kyiv Polytechnic Institute" of the Ministry of Education and Science of Ukraine, Kyiv, 2016. The thesis is dedicated to solving a topical research and applied task of developing the small-scale "just in time" production scheduling information technology. This information technology leads to increased efficiency of industrial systems' functioning by constructing close to optimal schedules in terms of time criteria. During the research, existing planning models and systems, scheduling methods, production scheduling systems, scheduling theory models and methods are reviewed. The application of the methodology of constructing PDC-algorithms for intractable combinatorial optimization problems to developing scheduling algorithms is described. The literature analysis is done, in which the works are identified that offer different approaches to solving scheduling problems under study. The small-scale production scheduling process is reviewed for enterprises consisting of an industrial sections set. Based on the latter observations, the tedious scheduling problem is decomposed into smaller ones enabling us to distinguish scheduling problems by the industrial sections. As a result, the methods for small-scale production scheduling are developed for the following problems: the problem of feasible scheduling for identical parallel machines in order to determine the latest starting time of performing tasks with common due date; the problem of feasible scheduling for uniform parallel machines in order to determine the latest starting time of performing tasks with common tough due date; the problem of scheduling for identical parallel machines in order to minimize the maximum deviation of ending times of performing tasks from the due date; the problem of scheduling for uniform parallel machines in order to determine the most uniform distribution of load. Properties of these problems are studied. Algorithms for initial schedule construction are given. Sufficient conditions for optimality and sets of tasks exchange operations are developed and used as a basis for the polynomial component of the PDC-algorithm. Auxiliary optimization problems are formulated, whose results are used to determine sufficient conditions for the problem of feasible scheduling for uniform parallel machines in order to determine the latest starting time of performing tasks with common tough due date and the problem of scheduling for uniform parallel machines in order to determine the most uniform distribution of load. Suitability of applying the proposed scheduling methods is grounded. The proposed methods' effectiveness is analyzed with the help of the proposed classification of individual scheduling problems. This classification is based on the number of tasks, their average duration, probability distribution, duration variance, and the variance of machines' productivity coefficients. During the experiments, series of tasks of different types are passed as inputs to the PDC-algorithm. As a result of the experiments, different permutations search strategies are studied. Problem subclasses are identified, for which the proposed methods yield almost perfect optimum. The information technology of small-scale "just in time" production scheduling is developed based on the proposed scheduling methods. All the necessary algorithms for the information technology are described. The tasks solved in order to develop this information technology include formation of a generalized technological production graph, scheduling dispatching of tasks completion at different industrial sections using the generalized technological graph. Experiments are conducted that prove the practical significance of the developed information technology and adequacy of the proposed models and methods. Keywords: schedule, scheduling theory, PDC-algorithm, production scheduling, small-scale production, just in time, information technology.
