Research On Meta-heuristic Methods For Distributed Shop Scheduling

Against the backdrop of increasing globalization of market and manufacturing,and in response to the rapidly changing market demand,the production workshop has been switched from the single factory to multi-factories,and from the centralized structure to the distributed structure.A distributed workshop production mode is formed as a result.Shop scheduling is an essential part in the distributed workshop production.Effective scheduling algorithms and optimization technology can optimize the production system,reduce the production cost,improve production efficiency and enchance economic benefits.Distributed shop scheduling problem is more complicated than the single shop scheduling.In particular,research on scheduling methods has attracted wide attention from both of academic and industrial circles.Many distributed shop scheduling problems are NP(non-deterministic polynomial)hard problems.Traditional scheduling methods,such as branch and bound method,mathematical programming method and heuristic rule,hardly obtain the optimal solution or their computation is too large.Meta-heuristics does not depend on solving problems,and can obtain more satisfactory solutions through global and local search.These advantages make it effective for solving scheduling problems,with important and valuable implications for both academic research and practical applications.This paper deeply studies the processing constraints widely existing in manufacturing system,such as no-wait,no-idle,due date,and proposes the imporved teaching-learning optimization algorithm and Memetic algorithm based scheduling method.Subsequently,the related results are extended to distributed shop scheduling problems,providing solutions to the distributed no-wait flow shop scheduling and the distributed assembly no-idle flow shop scheduling problems.The main research work is as follows:(1)In view of the lack of teaching-learning optimization algorithm,a collaborative learning mechanism based on the probability distribution model is proposed from the perspective of probability theory.The probability model is embedded into the teaching or learning stage,i.e.,the probability distribution is used as a teacher or information exchange platform.For the no-wait flow shop scheduling problem,a discrete teaching-learning optimization algorithm based on the probabilistic learning phase(HDTPL)is proposed.This algorithm first uses the neighborhood search to imitate the teaching phase,and employs the probabilistic model as a knowledge collection platform.Each student can learn through the exchange with the platform,which realize the self-learning between students.The testing results based on benchmark testing instances varify the effectiveness and superiority of HDTPL.(2)The distributed no-wait flow shop scheduling problem is studied,and the mixed integer programming model of this problem is established.Several the speed-up methods of neighborhood moves are proposed which can reduce the computational complexity.For the distributed no-wait flow shop scheduling problem,three iterated greedy algorithm IG-VNS,IG_VND,IG_RNS which combine variable neighborhood search,variable neighborhood descent,and random variable neighborhood framework.A large number of simulation experiments show that the proposed algorithms are better than other current distributed shop scheduling algorithms.(3)A multi-objective distributed no-wait flow-shop scheduling problem with sequence-dependent setup time is studied,and the performance criteria considered are the makespan and the total weight tardiness.Setup must be performed between the completion of one job and the start of another job on each machine.To solve the above problem,a Pareto non-dominated solution based estimation of distribution algorithm is proposed.Three probabilistic models,i.e.,the probability of the jobs in empty factory,the two jobs in same factory,and the adjacent jobs are constructed.Based on the probabilistic models,a sampling method with reference template is presented to generate offspring individuals,and the multi-objective neighborhood search are applied to the archieve set and offspring individuals.Experimental results indicate that the proposed algorithm outperforms other compared algorithms and the obtained solutions has good distribution and approximation.(4)For the no-idle flow shop scheduling problem,a Memetic algorithm based on hybrid node and edge histogram model(MANEH)is proposed.The MANEH considers the order of jobs and the similar jobs block,and employs a random sample method based on hybrid node and edge histogram model,which can eliminate aimless job selection.In the local search phase,the random referenced neighborhood searching method and the acceptance criteria based on simulated annealing are added to the variable neighborhood search,which further improves the local search ability.The experiment based on the large-scaled testing instances verifies the superiority of MANEH.(5)For the no-idle flow shop scheduling problem with due date constraint,this paper proposes a discrete teaching-learning meta-heuristic based on probabilistic teaching to solve it.In the teaching phase,a probabilistic model is established based on the elite learners and the best learner,and a series of position sequences are generated by sampling from the probabilistic model.The concept of consensus permutation is used to replace the mean individual in the original teaching-learning phase.The new individuals are generated according to the position sequences and the consensus permutation.In the learning phase,according to different levels of students,all students are divided into three layers,and the proposed learning phase adopts the order of top-down to spread the knowledge.The comparisons with several current advanced algorithms varify the superiority of HDTLM.(6)A distributed assembly no-idle flow shop scheduling problem is studied.For the shortcomings of job assignment rule,a new job assignment rule is proposed,which makes the process order of the corresponding jobs as compact as possible,then the assembly stage of the product can start as early as possible.This leads to the reduction of the assembly waiting time.For the distributed assembly no-idle flow shop scheduling problem,a hybrid iterated local search(HILS)and a hybrid variable neighborhood search algorithm(HVNS)are proposed.The performance of HILS and HVNS are demonstrated to be superior to other related algorithms significantly in the same field by solving the benchmark instances.