Research On A Single Machine Scheduling Problem Based On Improved Ant Colony Algorithms

Single machine scheduling (SMS) problem is an important production scheduling problem. In theory, single machine scheduling can be seen as the special form of other scheduling problems, and a subsystem of the complex machine scheduling system. So, researching deeply on the single machine scheduling problem can make us understand better the structure of complex scheduling system. In the production practice, complex scheduling problems can be often divided into a number of SMS problems to solve. SMS problem is also a kind of classical NP problem, and the algorithm for solving SMS problem can provide us the basis of solving complex ones. Therefore, it is important to design a simple but efficient algorithm for SMS.Ant Colony Optimization (ACO), which inspired by the foraging behavior of true ants in the nature, is an intelligent heuristic algorithm. With the help of information, ants can always find the shortest path to the food. Solution construction procedure of ACO in the search is just to build a complete solution by adding continuously solution elements to it. So in this sense, the SMS is very suitable for solving by ACO because of the attribute as a multi-stage decision making. Moreover, the characters, such as systematic, self-organization, distributed computing and positive feedbacks, make ACO superior to other algorithms when solving SMTWT. However, when in practice use there . has been some shortcomings as more computation time, easily trapped in local minimum and so on. Therefore, we propose some methods to improve the performance of ant system, and develop several ACO algorithms for solving SMS.In this dissertation, the characteristics and structure of a kind of SMS problem is studied, and the emphasis of this research is to design some effective algorithms for solving this kind of SMS problem, accordingly several improved ACOs are proposed. Specifically, the main content of this paper are as follows:1,The concept of single machine scheduling problem and the research background of this dissertation are proposed firstly. Then the significance of SMS problem is discussed from the theoretical and practice aspect, and the theoretical models and the construction graph of SMS are proposed to illustrate the characteristics of SMS problem, which are summarized later. Moreover, the characteristics of ACO are also analysed in Chapter 1, and a framework in general sense of ACO based on the modular design is put forward. Then the feasibility and advantege about solving SMS by ACO are analysed from theoretical point of view. At last, the related issues about SMS, SMTWT and ACO are briefly analyzed and summarized to propose existing disadvantage. So the emphasis of this dissertation is to design a favorable algorithm for solving SMTWT. 2,Different ideas for designing main function modules of ACO are summarized according to technique and theory aspects in order to analyse the disadvantages of ACO, based on which an improved ACO, DPBAC algorithm, is proposed for general combinatorial optimization problems. In DPBAC algorithm, sevaral aspects of basic ACO are improved, including that introducing branching method to choose starting points, improving state transition rules, introducing mutation method to shorten tours, improving pheromone updating rules and introducing conditional dynamic perturbation method. Moreover the convergency of DPBAC algorithm is proved. By experiments, the advantages of DPBAC algorithm, that can shorten the calculation time and avoid the local optimum, are proved. Furthermore, compared with other kinds of improved ACO, DPBAC algorithm has its own merits.3,A strong NP-hard SMS, Single Machine with Total Weighted Tardiness(SMTWT) problem, is studied. Firstly the variables and the model of SMTWT in general sence are defined, then the articles about the research of SMTWT problem are summarized from the points of additional constraints, heuristical rules and solving algorithms. Based on DPBAC algorithm, an improved ACO for SMTWT problem, AC_SMTWT algorithm, is proposed, and the parameters of which are tried to be theoretically concluded from searching mechanism of algorithm rather than only from experiments. The data obtained from benchmark experiments show that not only on the calculation time but also on the solution, AC_SMTWT algorithm perform better than Genetic Algorithm, even superior to other improved ACO algorithm at some aspects.4,A SMTWT model based on an improved ACO algorithm using Q-learning is studied in order to avoid the complex parameter selection in AC_SMTWT algorithm for solving SMTWT problem. Firstly, the multi-stage decision making model of SMTWT problem is proposed, and the Markov properties of SMTWT and ACO are concluded. In the following, the flow of ACO is explained by Q-learing theory. Then the application of Q-learning to the single machine scheduling is summarized, and the disadvantages of look-up table for estimating Q function value are analyzed, therefor a BP neural network is proposed to estimate Q function value. Based on these, an improved ACO using Q-learning, AC_Q algorithm, is proposed for SMTWT problem to avoid the complexity of AC_SMTWT algorithm to choose parameters. In AC_Q algorithm, the characteristics of Q-learning, which are the environment-independence of Q function and the learning ability of Agents, are combined with the advantages of ACO, which are the distributed calculation, positive feedback and so on. As a consequence, the intelligence and stability of ACO are improved, which are proved by the experiments at last.In conclusion, SMS problem is very important not only on theoretical aspect but also on practical aspect. However, SMS is NP hard problem that is critical to find a good solving algorithm. In this dissertation, an improved ACO algorithm, DPBAC, is firstly proposed for general combinatorial optimization problems. Then based on DPBAC, an improved ACO for SMTWT problem, AC_SMTWT, is proposed. At last, to solve the disadvantage of AC_SMTWT, an ACO algorithm based on Q-learning is proposed. So these three improve ACOs have relations with each other, and they provide new theories and methods for SMTWT or other combinatorial optimization problem, also extend the research of theory and application of ACO.