Optimization Of Scheduling Malleable Tasks On Single Stage Of Nonidentical Machines

Along with economic globalization, marketing competition becomes intensive further in China and worldwide. Market demand for products has been featured in diversification, personalization and customization. The production orders in small or medium scale tend to increase. To keep the edge in the marketing competition, enterprises have to reduce production costs as well as to improve production efficiency and products quality. The thesis considers a special manufacturing environment of make-to-order quartz processing enterprise. The tasks for scheduling are malleable and each has a due date with penalty for tardiness. The considered production stage is the bottleneck factor of order tardiness in the whole manufacturing process, and there are several equipments or machines in common function at the stage. Each equipment or machine has distinctive processing efficiency and processing costs. The study aims to minimize the total costs in two aspects of the processing costs and the tardiness penalties to find the optimal schedule solution.After field investigation in the quartz enterprise, features and characteristics in the manufacturing process are analyzed. The concerned problem in the thesis is abstracted and defined as the optimization of scheduling malleable tasks on single stage of nonidentical machines. There are mainly four parts in this thesis:(1) On the basis of relevant literatures up to date, the shop-floor scheduling problem, parallel machine scheduling problem and malleable tasks scheduling problem are reviewed; comparative analysis is conducted with regard to the concerned problem.(2) According to the characteristics of the problem, the scheduling problem is formulated by mathematical model in terms of optimization objective, constraints and assumptions.(3) To solve the problem model, a dedicated Branch and Bound algorithm is designed to obtain the exact solution of the optimal schedule; the computation procedures are illustrated by problem instances and the desired results.(4) With respect to the problems in comparatively large-scale, a Genetic Algorithm is designed to adapt to the problem characteristics in aspects of chromosome encoding and evolution operators:crossover and mutation; the effectiveness and stability of GA are analyzed with computational experiments and compared with B&B algorithm.