Research On Batch Scheduling With Non-Identical Jobs To Minimizing Total Weighted Completion Time

For industries of manufacturing,textile,and logistics,and so on,studies of scheduling on parallel batch processing machines(SPBPM)to minimize the total completion time(TCT)is of great theoretical significance and application value,because it can satisfy the customers,decrease the inventory,and increase the profits of companies.Based on the current studies,this thesis extends to investigate the new problem of SPBPM to minimize total weighted completion time(TWCT)considering non-identical job sizes and processing time.After analyzing the features of the problem,this thesis constructs the mixed integer programming model and proves the NP-hardness of the problem.Then an algorithm for computing the problem is given.To address the studied problem,a heuristic and a meta-heuristic algorithm based on ant colony optimization(ACO)with two different pheromone strategies are proposed,respectively.In order to improve the performance of ACO algorithm,two strategies of pheromone are presented.Different from the values of influence factors set to be deterministic in traditional ACO algorithm,a scheme of dynamic influence factors is designed so that the role of pheromone modulated dynamically during the iteration.In order to ensure the guidance of pheromone to ant colony effectively,moreover,based on analyzing the problem,two types of different heuristic information is used to direct the ants to search.Finally,for the solution constructed by each ant,the structure of the solution is further optimized by using the local optimization strategy oriented to the problem to improve the quality of the solution.In order to verify the effectiveness of the algorithms,a series of simulated experiments are designed to compare the proposed algorithm and the other related algorithms.Moreover,Wilcoxon signed-rank test is employed on the comparative experimental results.Both the results of both the comparative experiments and the statistical experiments show that the proposed ACO-based algorithms outperform the other compared experiments.