Some Researches On Job Shop Scheduling Problems With Constaints Based On Metaheuristics

With the increasing competition in the market and the development of science technology and economy, the tread of enterprise modernization is irreversible. As the pillar industries of the national economy, Manufacturing needs not only the improvement of production and processing technology, but also advanced management technique and the best production and operation management plan, to improve enterprise’s overall productivity and the core competitiveness. Reasonable and efficient scheduling strategy is the key point of improving an enterprise’s management skills to make full use of current resource and greatly increase the enterprise’s productivity.Generally, production scheduling problem has various features with different domains and applications. Job Shop Scheduling Problem (JSSP) is one of the most characteristic scheduling problems and the most difficult combination optimization problems. The NP-hard feature of the problem determines that there exists no polynomial algorithm can obtain the optimal solution in limited time. Since the1980s, metaheuristic algorithms, which originated from an imitation of biological, physical processes and human behavior, attracted the attention of many international and domestic scholars. The metaheuristic algorithms have the characteristic of fast convergence rate, high efficiency, low dependence to the problem, which offer new ideas and orientation to solve JSSP. But because of the omission of constraints, the theory research on JSSP is hard to be used in practical production. Based on the background above, the article makes extending study of JSSP, combined with multi-object, no-wait and flexibility. The main research achievements and innovation point are as follows:(1) For the multi-objective job shop scheduling problem (MJSSP), a quad-space cultural genetic tabu algorithm (QSCGTA) is proposed to minimize the average flow time and makespan. In the proposed QSCGTA, a novel bi-directional shifting for the decoding process is incorporated with the operation-based representation to fulfill the calculation of objectives; moreover, a novel cultural structure in containing double brief spaces and population spaces is presented, and these spaces deal with different levels of populations globally and locally by applying genetic and tabu search separately and exchanges information regularly to make the process more effectively towards promising areas, along with modified multi-objective domination and transform functions; in addition, an orthogonal experiment design is employed to provide a receipt for turning the adjustable parameters of the QSCGTA. The computational results presented significantly prove the effectiveness and efficiency of the cultural-based genetic tabu algorithm for multi-objective job shop scheduling problem.(2) Considering the widely existence of no-wait constraints in many production processes and few relevant literatures, a combined complete local search with memory (CCLM) is proposed to deal with no-wait job shop scheduling problem (NWJSSP). The problem is decomposed into two sub-problems, the sequencing and timetabling problem; a new efficient combined non-order timetabling method, coordinated with objective of total tardiness, is proposed for the timetabling problems; as for the sequencing one, we have presented a modified complete local search with memory combined by catastrophe operator and distance counting. The entire algorithm was tested on well-known benchmark problems and compared with several best existing algorithms. Computational experiments show that our proposed algorithm performs both effectively and efficiently.(3) Based on the above research, a multi-objective combined complete local search with memory (MCCLM) is presented for the multi-objective no-wait job shop scheduling problem to minimize makespan and total tardiness, an initialization based on the LPT, SPT, EDD heuristics is incorporated into the random initialization to generate an initial solution with certain quality and diversity; meawhile a multi-object combined bi-direction timetabling strategy is designed by taking the two objectives into consideration; moreover, some special strategies based on Pareto seletion are proposed; and reasonable parameters of CCLM were determined by performing experiments to identify the tradeoff between effectiveness and efficiency. Various experiments on benchmark problems proved the feasibility and effectiveness of the proposed algorithm.(4) A multi-objective modified biogeography-based optimization (MMBBO) is brought up for the multi-objective flexible job shop scheduling problem (MFJSSP) to minimize makespan, total workload of machines and maximal machine workload. The MMBBO algorithm applies a double coding scheme with operation-based and machine-based vector; a special multi-machine shifting strategy is proposed to decoding the vectors to scheduling solutions; several discrete operators in BBO, such as emigration, immigration and mutation are designed based on non-dominated sorting and a special operator based on local search, instead of mutation, is applied to non-dominated solutions. Comparisons on Kacem and BRdata instances, under both single objective and multi-objective context, indicate the superiority of the proposed MMBBO algorithm in terms of effectiveness and efficiency.