An Algorithm For Job-shop Scheduling Problem With In-tree Precedence Constraints On Jobs

Nowadays,the core competitiveness of enterprises that supporting further development in the market has shifted to product diversity and personalization.In order to improve the economic efficiency of enterprises,the scheduling problem of manufacturing systems has increasingly received widespread attention.Job-shop scheduling problem(JSP)with in-tree precedence constraints on jobs is a common scheduling problem in manufacturing workshops,which has generally existed in assembly discrete manufacturing workshops and multi-variety small batch production workshops.This JSP is constrained by the dual production sequence at the jobs level and the process level,and the problem of excessive WIP inventory often appears in actual scheduling,thus it is a more complex NP-hard problem than the classic JSP.On the basis of deep insights of JSP and optimization algorithms in terms of theoretical and applied research,this paper designs an effective algorithm for JSP with in-tree precedence constraints on jobs.The main innovations of this article and its related work are as follows:1.After sorted out and summarized the research results of JSP in the past 70 years,this paper founded that genetic algorithm is the most widely used and feasible in this field;backward scheduling can effectively control WIP inventory;there are few research on JSP with in-tree precedence constraints on jobs and applying backward scheduling to solve JSP.Aiming at the main pain points encountered in the actual production workshop,combining the advantages and disadvantages of each optimization algorithm,this article chooses to design an algorithm which combines genetic algorithm and backward scheduling to solve the JSP with in-tree precedence constraints on jobs.2.Focusing on the scheduling goal of reducing WIP inventory,4 suitable scheduling KPI(performance evaluation indicators)are summarized by this article.3.The constraint relationship of JSP with in-tree precedence constraints on jobs is complex,in order to sort out the constraints on the production sequence in both the internal and external parts of the jobs,this paper proposes to build dendrograms and layer on all the jobs based on the sales order.After the layering,there is no production sequence constraint between jobs in the same level,also simplifying the in-tree precedence constraints between jobs into chain precedence constraints between sets of jobs in each layer.On this basis,the paper describes the JSP with in-tree precedence constraints on jobs and establishes a mathematical model for it,constructs an algorithm framework combining with the idea of backward scheduling.The core of this framework is the in-tree-JSP backward genetic algorithm,which is designed for the problem in this article.4.According to the characteristics of the problem in this paper,the main designs of the in-tree-JSP backward genetic algorithm include: redefine the coding method based on process,and propose the process insertion method in backward as the decoding method,then the scheduling schemes with less WIP inventory and shorter production cycle can be decoded;the paper also proposes random initialization methods based on jobs and sales orders,the initial population generated by the former has better diversity and excellent individuals,while the initial population generated by the latter has outstanding performance in maximizing completion synchronization;besides,in order to improve the local search competency of algorithm,the paper proposes a neighborhood search mutation operator based on jobs to mutate chromosomes.Last but not least,in-tree-JSP backward genetic algorithm is realized by using Python and verified by one actual case.Experiments show that in-tree-JSP backward genetic algorithm has good convergence,feasibility and effectiveness,shortens the processing waiting time of the original workshop by 44.29%,reduces the WIP inventory,and achieves 100% on-time delivery rate.