Research On Batch Scheduling Algorithms With First Job Selection Strategies

Scheduling problem is a kind of combinatorial optimization problem with a wide application background.The main purpose of scheduling is to allocate the limited resources reasonably to obtain the maximum economic benefit.With the complexity of scheduling problem,it is impossible to solve the scheduling problem only by experience.At this time,an efficient scheduling algorithm is particularly important.Due to the complexity of scheduling process and scheduling environment,scheduling problems are constantly diversified,and many scheduling problems with different characteristics have evolved.Among them,the batch scheduling problem is an extension of classical scheduling problem.The batch scheduling problem is a problem that a certain number of jobs can be processed simultaneously by the same batch machine.It is widely used in many scenarios,such as logistics transportation,petrochemical industry,and so on.Unlike classical scheduling problems,in batch scheduling problem,the jobs are first batched,and then the jobs are processed non-interrupted by batch machines.After the job is batched,the attributes of the batch are determined by the attributes of the job in the batch and the machine attributes of the batch is located.The batch scheduling problem is not satisfied with the optimization of a single objective,and gradually considers the optimization of multiple mutually exclusive objectives,forming a multi-objective batch scheduling problem.Ant colony algorithm is an evolutionary algorithm based on ant foraging behavior.Unlike other evolutionary algorithms,ants in ant colony algorithms are gradually constructing feasible solutions.Due to the constructive of ant colony algorithm,ant colony algorithm has been widely used in batch scheduling in recent years.Ant colony algorithm guides ants to construct new feasible solutions by pheromone and heuristic information.In the batch scheduling problem,the pheromone records the historical weight relationship of the jobs in the same batch,and guides ants to search the historically excellent solution space.Heuristic information is usually designed based on batch scheduling experience,guiding ants to search for the solution space that people desired.Through pheromone and heuristic information,the search space of the batch scheduling problem is effectively reduced and the search quality of solution is improved.Firstly,this thesis studies to minimize the makespan for scheduling the jobs with dynamic arrivals on batch process machines.According to the characteristics of the problem,a new lower bound algorithm is proposed to measure the performance of the algorithm,and the effectiveness of the proposed lower bound algorithm is proved.According to the influence of the first job on the batch construction process,the weak constraint criteria and two first job selection strategies based on the weak constraint criteria are proposed for the selection of the first job in the batch construction process.Two selection strategies are proposed based weak constraint criteria,and used to improve the ant colony algorithm.The simulation results show that the effectiveness of weak restriction in the batch construction process and the high probability selection strategy with large job size is better than the average probability selection strategy.Secondly,this thesis applies a batch scheduling algorithm to minimizing the makespan and the maximum tardiness for scheduling the jobs with non-identical sizes and release times on the parallel batch process machines.In order to reduce the search space,a new first job selection strategy and a type of heuristic information is designed.To improve the neighborhood search ability of the ant colony algorithm,a new role is introduced to enhance the search ability of the algorithm in the domain of non-dominant solutions.The simulation results demonstrate the effectiveness of the proposed strategy to reduce the search space and the new role of ant colony algorithm.Finally,this thesis also sum up the research contents of this article and make some prospects for future research in related fields.