Research On Hybrid Ant Conoly Optimization Algorithm With Incompatible Job Families

Scheduling problem has always been a hot issue, which has been widely applied to various industrial fields. With the development of the social economy, the pruduction environments are gradually becoming more complicated. From the early traditional scheduling to modern ones, the models of scheduling are changed with the production enviroment, job features, and the objective functions. The more sophisticated of the production conditions, the more difficulty of solving this problem. Batch scheduling is one of the important branches of scheduling problem. Different from the classical scheduling, a machine can process more than one job at the same time in batching scheduling. Thus, instead of being shceduling on the machines directly, the jobs should be grouped into batches, which are then scheduled on the machines. It makes the problem relatively more complex. And the two steps are critical for enhancing the equipment utilization and shortening the delivery dates.The research on batch scheduling generally starts from dealing with the simple single machine evironment and unit-size jobs. With changing the production environments and considering more job features, the batching scheduling on multiple machines is generated. The latter has become the main research field of batch scheduling, including charactes of batching processing, dynamical job arrivals, non-identical job sizes, incompatible job families, and so on. The more job features considered, the more complex of the problem and the more difficult of finding the approximation of the solution. The studied problem in this thesis is the batching scheduling with dynamic job arrivals and incompatible job familes.Firstly, two applications, the supply chain scheduling problems and the production of garment enterprises,are introduced. The batch scheduling problem with incompatible job families is then described. And the three-parameter expressions of general scheduling problems are provided, as well as their current research status.Secondly,we describles some heuristics and meta-heuristic that to solve the batch scheduling problem, and explain the specific processes of each algorithm.Thirdly,we describes an improved Max-Min ant system for the studied problem of minimizing the makespan with incompatible job families. A detailed description of the specific processes of the algorithm in this chapter which describles the focus heuristic information of ant colony algorithm.Forthly,in order to verify effectiveness of the algorithm,the performances of our algorithm and some other algorithms are compared.The results show that t he improved algorithm has good performance to solve,you can find quality opti mum solutions.Lastly,we summarizes the full text and the prospect of future research directions.