The Algorithm Research On No Wait Flow Shop Scheduling Problem Base On Heuristics Rule And Factorial-Code

Scheduling problems play an important role in the manufacturing system.As a kind of flow shop,no-wait flow shop problems are widely used in many industries.Such as iron production,mining,logistics,medical industry and food industry.In the NWFSS,n jobs will be processed on m machines.Each of n jobs has a predetermined processing time.The processing of each job must be successive.In other words,the waiting time between the operations of a job on all machines is zero.Each job can be processed at most on one machine,and each machine can process at most one job.The starting time of jobs and machines can be regarded as zero.The objective of the NWFSS is to schedule the job sequence to achieve an optimal makespan.The transitional schedule algorithm could not satisfy the real process of product.So the theory for solving no wait flow shop schedule problem still hot.The main research contents are as follows:1.For deflating the search space a heuristic optimization algorithm based on search area segmentation and Fast Fourier Transform(HSAS/FFT)is proposed in this paper.In the proposed algorithm,the landscape of the whole solution space is divided into different connected areas by Fast Fourier Transform(FFT).F irstly,the frequency of each dimension can be acquired by the Fast Fourier Transform(FFT).The frequency with little vibration amplitude will be filtered.The search space is divided by 1/2 cycle or small er cycle to ensure that each solution space is unimodal.Secondly,the single divided areas can be found in the local optimal solution by making use of Binary Search algorithm.2.For the Gant a jigsaw puzzle inspired algorithm(JPA)for solving NWFSSP with the objective of minimizing makespan is proposed.The principle of JPA is simple,and the core idea of JPA is to find the best match for each job until all the jobs are scheduled.JPA is not a stochastic algorithm;the process of searching the solution in JPA does not have random behavior,so it has strong robustnes s.Compared with other heuristic algorithms,JPA does not adopt an iterative way to search global optimum.Thus,it performs a fast convergence speed.Besides,it is not required to set initial values in JPA,which can reduce the influence of human factors on the algorithm performance.3.For the Landscape a population-adaptation particle swarm optimization which based on factorial-code(PAPSO-F)to address no-wait flow shop scheduling problem with the objective to minimize makespan,is proposed.Firstly,the factorial-code(FC)is employed,which is a way to map the scheduling sequences to natural numbers one-to-one correspondingly.Secondly,the fitness landscapes of different scheduling models are listed based on factorial-code.And the population-adaptation particle swarm optimization(PAPSO)is utilized to solve no-wait flow shop scheduling problem after analyzing the fitness landscape.In the PAPASO,in order to measure population diversity,PA is calculated by means of population Euclidean distance.And the normal distribution is adopted to randomly initialize the population to increase the diversity when the population diversity is decreased.