Study Of Hybrid Algorithm For No-wait Integrated Scheduling Problem

The integrated scheduling problem is a scheduling problem in which machining and assembly are considered simultaneously.This kind of scheduling fully takes into account the characteristics of individual product production processes: the structural characteristics and manufacturing parameters of different products vary greatly;it is common for a large number of non-standard workpieces to be assembled and then processed in depth.No-wait processes are widespread in the steel casting,precision assembly,and food industries,which require processes subject to no-wait constraints to be processed without interruption.For example,in cryogenic assembly operations,the cryogenically treated workpiece needs to be assembled immediately,otherwise,uneven temperatures may occur,resulting in assembly failure and failure to meet accuracy requirements.Therefore,the study of the No-wait Integrated Scheduling Problem(NWISP)can optimize the production process of personalized products as a whole and achieve the effect of increasing production and efficiency.The specific research work consists of the following components.For the static NWISP problem,a static NWISP mathematical model is established with the objective of minimum completion time,and a hybrid method based on particle swarm and genetic algorithm(GA-PSO)is designed for the solution.The algorithm draws on the information flow relationship expressed by the velocity displacement equation,based on genetic operations,and embeds the update mechanism of PSO into the GA algorithm,forming a hybrid algorithm based on a dual population update strategy.In order to deal with the case where the number of no-wait immediately preceding processes is greater than one,the no-wait virtual process encoding and decoding algorithm based on the earliest adaptation strategy is designed so that a set of no-wait processes can be inserted into the Gantt chart while maintaining the tree constraint relationship.The experimental data show that the designed GA-PSO algorithm can obtain a shorter completion time than the control algorithm,which verifies that the proposed algorithm is effective and feasible.For the dynamic NWISP problem,an event rescheduling strategy is used to convert the dynamic production process into a static scheduling problem that is continuous in time,with the minimization of the total drag time as the scheduling objective.At each event moment,the designed GA-VNS(Genetic Algorithm and Variable Neighborhood Search)hybrid algorithm is used to reschedule the unfinished tasks and the newly arrived tasks at that moment.The designed GA-VNS considers the situation of flexible manufacturing resources,so it needs to design a conflict adjustment method for solving the problem that the machine may have conflict when the number of immediately precedent no-wait operations is greater than 1.Experimental data verify that the proposed optimization method is effective and feasible,and can obtain a better scheduling scheme than the control algorithm.There are transportation constraints and flexible manufacturing resources in the multi-shop NWISP problem.In the case of multi-shop,when an operation is finished,the resource needs to be transported to the shop where the machine of its immediate successor is located,and the transportation time of different shops needs to be considered.In order to deal with the multi-shop situation,a conflicting machine adjustment method applicable to multi-shop flexible resources is proposed to ensure that the machine encoding string is always in the feasible solution without conflict when the number of no-wait immediately precedent operations is greater than 1.A virtual process decoding method applicable to multiple shops is proposed to ensure the multiple shop constraints and no-wait constraints.Based on these improved methods,an improved GA-VNS is formed to optimize globally and locally at the same time.Experimental results show that the proposed improved algorithm not only adapts to the multi-shop NWISP problem but also works better.An improved GA-PSO is proposed to solve the NWMISP(No-wait Multi-objective Integrated Scheduling Problem)problem.To deal with the multi-objective Pareto solution aggregation problem,a selection strategy based on the Niched is used to filter out more diverse individuals.The experimental results show that the proposed improved algorithm is effective and feasible.In some production environments,machine tool needs to be warmed up before it can be put into use.However,keeping machine in working order at all times in discrete production activities can significantly increase energy consumption and incur unnecessary costs.The warm-up time is converted into a special setup time,i.e.,the setup time is related to the initial state of the machine.A dual-objective mathematical model with minimization of the total tardiness and total setup time is developed.In order to solve the model using the GA-PSO,a decoding method driven based on machine idle signals is proposed which can handle both the machine-state-related setup time and the no-wait constraint.Using randomly generated examples and enterprise instances as comparison data,experimental results show that the proposed algorithm is not only efficient and feasible,but also has better scheduling quality than the control algorithm.