Research On Structural Properties And Heuristic Algorithms For Flow-shop Scheduling Problems

Flowshop scheduling problem (FSP) has been widely investigated in theresearch area of manufacturing systems. Heuristic algorithms based on thestructural properties are mainstream approach to solve the problem. Focusing onthis direction, the contribution of the thesis can be concluded as follow:(1) Up to now, the NEH algorithm is the best heuristic approach to solveFSP. However, in large-scale problems, it takes quite long time for the NEHalgorithm to find an approximate optimal solution. In Chapter2, two newtechniques are proposed to improve the NEH algorithm. Firstly, to reduce therunning time, block properties are developed and introduced to NEH algorithm.Secondly, to obtain solutions with smaller makespan, tie-break rules are applied.Simulation results show that these two techniques perform well in improving theNEH algorithm.(2) For permutation flowshops with two machines or more than twomachines, as the number of jobs tends to infinity, the properties of asymptoticdistribution of makespan are proposed. In Chapter3, we introduce severalconclusions in queuing theory to the scheduling problem, and convert thedistribution of makespan to the distribution of waiting time in the queue. Intwo-machine conditions, the asymptotic distribution of makespan is proved tobe the right half of a normal distribution. In m-machine conditions (m>2), theasymptotic distribution of waiting time is proved under certain assumptions, andthe bounds of probability distribution functions of waiting times are given.(3) No-wait flowshop scheduling problem is widely investigated because ofits practical application and specific properties. However, the total tardinesscriterion hasn’t been much considered. In Chapter4, six heuristic approachesare proposed for no-wait flowshops with total tardiness criterion, among whichthe modified NEH algorithm (MNEH) is verified to be the best. Also, a speed-uptechnique is introduced to MNEH to reduce the computational time in certain cases. By numeral experiments and analysis, we evaluate the performances ofvarious heuristics and find out that MNEH is a satisfactory algorithm dealingwith this problem.