Flexible job shop scheduling problem(FJSP)is the core decision-making problem of intelligent manufacturing production management.The Harris hawk optimization(HHO)algorithm,as a typical metaheuristic algorithm,has been...Flexible job shop scheduling problem(FJSP)is the core decision-making problem of intelligent manufacturing production management.The Harris hawk optimization(HHO)algorithm,as a typical metaheuristic algorithm,has been widely employed to solve scheduling problems.However,HHO suffers from premature convergence when solving NP-hard problems.Therefore,this paper proposes an improved HHO algorithm(GNHHO)to solve the FJSP.GNHHO introduces an elitism strategy,a chaotic mechanism,a nonlinear escaping energy update strategy,and a Gaussian random walk strategy to prevent premature convergence.A flexible job shop scheduling model is constructed,and the static and dynamic FJSP is investigated to minimize the makespan.This paper chooses a two-segment encoding mode based on the job and the machine of the FJSP.To verify the effectiveness of GNHHO,this study tests it in 23 benchmark functions,10 standard job shop scheduling problems(JSPs),and 5 standard FJSPs.Besides,this study collects data from an agricultural company and uses the GNHHO algorithm to optimize the company’s FJSP.The optimized scheduling scheme demonstrates significant improvements in makespan,with an advancement of 28.16%for static scheduling and 35.63%for dynamic scheduling.Moreover,it achieves an average increase of 21.50%in the on-time order delivery rate.The results demonstrate that the performance of the GNHHO algorithm in solving FJSP is superior to some existing algorithms.展开更多
We investigate the online scheduling problem on identical parallel-batch machines to minimize the maximum weighted completion time.In this problem,jobs arrive over time and the processing times(of the jobs)are identic...We investigate the online scheduling problem on identical parallel-batch machines to minimize the maximum weighted completion time.In this problem,jobs arrive over time and the processing times(of the jobs)are identical,and the batch capacity is bounded.For this problem,we provide a best possible online algorithm with a competitive ratio of(√5+1)/2.Moreover,when restricted to dense-algorithms,we present a best possible dense-algorithm with a competitive ratio of 2.展开更多
In recent years,scholars have made many research results on job-shop scheduling(JSP)problem,especially in single objective such as the maximum completion time.But most of the actual system scheduling problems are more...In recent years,scholars have made many research results on job-shop scheduling(JSP)problem,especially in single objective such as the maximum completion time.But most of the actual system scheduling problems are more than one object.Therefore,the research of multi-objective scheduling problem is very important and meaningful.In this paper,we proposed a multi-objective scheduling model which adopts weighted sum method to optimize two important indexes(makespan and total flow time).Genetic algorithm(GA)has diversified global search ability,while simulated annealing(SA)combined with tabu search(TS)have intensified capabilities in local neighborhood search.To overcome the drawback of the GA,we proposed a new hybrid GA(NewHGA)which produces initial solutions by GA firstly,and then take SA operator incorporate TS operator to search in the local space.By adding the novel local search strategy,the diversity of solutions will be improved greatly so that it can ensure the algorithm jump out of the local optimal value.We test this algorithm using the benchmark instances of different sizes taken from the OR-Library,and the results show that the algorithm is efficient than another hybrid algorithm.展开更多
文摘Flexible job shop scheduling problem(FJSP)is the core decision-making problem of intelligent manufacturing production management.The Harris hawk optimization(HHO)algorithm,as a typical metaheuristic algorithm,has been widely employed to solve scheduling problems.However,HHO suffers from premature convergence when solving NP-hard problems.Therefore,this paper proposes an improved HHO algorithm(GNHHO)to solve the FJSP.GNHHO introduces an elitism strategy,a chaotic mechanism,a nonlinear escaping energy update strategy,and a Gaussian random walk strategy to prevent premature convergence.A flexible job shop scheduling model is constructed,and the static and dynamic FJSP is investigated to minimize the makespan.This paper chooses a two-segment encoding mode based on the job and the machine of the FJSP.To verify the effectiveness of GNHHO,this study tests it in 23 benchmark functions,10 standard job shop scheduling problems(JSPs),and 5 standard FJSPs.Besides,this study collects data from an agricultural company and uses the GNHHO algorithm to optimize the company’s FJSP.The optimized scheduling scheme demonstrates significant improvements in makespan,with an advancement of 28.16%for static scheduling and 35.63%for dynamic scheduling.Moreover,it achieves an average increase of 21.50%in the on-time order delivery rate.The results demonstrate that the performance of the GNHHO algorithm in solving FJSP is superior to some existing algorithms.
基金This research was supported by the National Natural Science Foundation of China(Nos.11571321 and 11401065)the Natural Science Foundation of Henan Province(No.15IRTSTHN006).
文摘We investigate the online scheduling problem on identical parallel-batch machines to minimize the maximum weighted completion time.In this problem,jobs arrive over time and the processing times(of the jobs)are identical,and the batch capacity is bounded.For this problem,we provide a best possible online algorithm with a competitive ratio of(√5+1)/2.Moreover,when restricted to dense-algorithms,we present a best possible dense-algorithm with a competitive ratio of 2.
基金support of the National Science and Technology Supporting Plan of China(No.2013BAF02B09)for the work done in this paper.
文摘In recent years,scholars have made many research results on job-shop scheduling(JSP)problem,especially in single objective such as the maximum completion time.But most of the actual system scheduling problems are more than one object.Therefore,the research of multi-objective scheduling problem is very important and meaningful.In this paper,we proposed a multi-objective scheduling model which adopts weighted sum method to optimize two important indexes(makespan and total flow time).Genetic algorithm(GA)has diversified global search ability,while simulated annealing(SA)combined with tabu search(TS)have intensified capabilities in local neighborhood search.To overcome the drawback of the GA,we proposed a new hybrid GA(NewHGA)which produces initial solutions by GA firstly,and then take SA operator incorporate TS operator to search in the local space.By adding the novel local search strategy,the diversity of solutions will be improved greatly so that it can ensure the algorithm jump out of the local optimal value.We test this algorithm using the benchmark instances of different sizes taken from the OR-Library,and the results show that the algorithm is efficient than another hybrid algorithm.
