Lysetskyi T. Information technology of job-shop problem under precedence constraints

The dissertation is dedicated to research of information technology (IT) of job-shop scheduling in systems with precedence constraints based on highly efficient job-shop scheduling methods. Thanks to formalization of precedence constraints, modification of aggregation and disaggregation procedures and the procedures of coordinated planning from earlier created three-level scheduling model (3LM), substantiation of reducing the planning problem by any of the five basic criteria to a single scheduling problem, operational (the third level of 4LM) and operative (the fourth level of 4LM) planning levels formalization and development of the algorithms for operational scheduling and adjustments, an integral set of models and methods was created for the first time — the four-level model (4LM) of job-shop scheduling. The 4LM implements an efficient approximation method for Multi-Stage Job-Shop Scheduling Problems (MSJSP) in social and economic systems with precedence constraints and limited resources and methods of operational and operative planning. 4LM includes the decision-making unit (DMU) as a separate component that takes decisions during production planning. The process of obtaining operational plan (third level of 4LM) based on results of coordinated planning (second level of 4LM) has been formalized: if optimality criterion is one of the five base criteria then the operational planning task is defined and solved as multi-stage job-shop scheduling problem (task or task group completion times become due times for multi-stage job-shop scheduling problem), an affective solving method use PDC-algorithms for single stage scheduling; if optimality criterion is synthetic (linear combination of base criteria) alternative methods for building operational plan were suggested. One of them is original modified method of coordinated planning. Two algorithms for coordinated plan correction were developed, which are used on the fourth level. It is shown that regardless of type of industry, operations processing order and an implementation of JSP, solving of scheduling problem by one of these five optimality criteria is reduced to obtaining a feasible solution of the JSP by criterion of earliest job start time maximization. It is shown that solving efficiency of the JSP depends on efficiency of the first level of 4LM. Therefore, efficiency of MWCT problem solving is studied and statistically substantiated. The efficiency of the PDC-algorithm and the approximation algorithm has been proven for the case when weights of all nodes of the precedence graph, except the final ones, are zero (MWCTZ problem). The mathematical models for solving a scheduling problem “Uniform parallel-machine scheduling with independent jobs whose start times are less than a common due date to minimize total tardiness” (MTTPM) (used at the fourth level of 4LM) have been created. Unlike others, the new method allows to get exact solution for problems with tens of thousands of variables in case of optimality criteria fulfillment otherwise approximate solution with evaluation of deviation from optimum. The MTTPM problem was also generalized to the case when some or all jobs must not violate the common due date. An approximation algorithm based on the sequential solution of two different MTTPM problems has been developed. Three statements characterizing the theoretical properties of the approximation algorithm are proved. These statements allow: finding conditions when the problem has no solution; finding sufficient conditions of conditionally-optimal solution (optimal under condition that schedule is found for given job set which all are non-delayed); finding statistically sufficient factors of solution optimality; finding the lowest limit of functional value of optimal solution. The problem properties have been investigated and theoretically substantiated. On the basis of 4LM, an IT for job-shop scheduling in systems with precedence constraints has been created. It was implemented as general-purpose job-shop scheduling information system. The system is used to automate the production planning process at the "LETA" enterprise (Mukachevo town). It can work with data of real production sizes — hundreds of thousands of jobs on thousands of machines.