On Flow Shop Scheduling Problems With Approximation Strategy And Its Applicaitons

Initially,flow shop model is established to solve scheduling problems of car assembly line,which is widely used in production.For a flow shop problem,a set of jobs has to be processed on each machine in an identical order.At any given moment,each machine can deal with one job at most,and each job can be processed only by one machine.Moreover,the process cannot be interrupted unless it is finished.The goal of flow shop problem is to find a schedule with a optimal objective function value.Most of flow shop problems are NP-hard,i.e.,optimal solutions of the problem cannot be found in polynomial time.Therefore,many researches of flow shop problems is to optimize solutions for fulfilling requirements of production.After investigating actual problems,a series of flow shop model are adopted to deal with these problems.Moreover,new approximate algorithms are proposed and the validity of the algorithms is verified by computer simulation.The main works and innovations are as follows:(1)The problem that different materials need different ordering policies in Baosteel procurement and supply chain systems is researched,a material order quantity model is presented and the empirical formula for material safety stock setting is given.In the practical application process,probability distribution of some variables cannot accurately be found,such that demand and consumption of materials are forecasted by gray model.The selection problem of order strategy in procurement supply chain systems is solved through forecasting the demand of materials,setting the safety amount of stock and using different models for different kinds of materials.The proposed model verified by simulation results has a strong practical significance providing users with a more practical ordering strategy.(2)Permutation flowshop is one of the most popular modelsin shop scheduling problems.For the permutation flowshop total weighted completion time problem,an effective heuristic algorithm is designed toobtain approximatesolutions forlarge-scale problemsin this paper.Moreover,a discrete differential evolution algorithm(DDE)based on amulti-point insertion method is proposed to solve moderate-scale problems.Finally,a set of random simulation experiments demonstrate the performance of the proposed algorithm.(3)No-wait flow shop problem is a kind of flow shop problem,which is widely used in steel production.This thesis mainly investigates the m-machines problem with the maximum delivery time criterion.At first,asymptotical optimality of Shortest Processing Time(SPT)first heuristic is proved for the problem.For evaluating the effectiveness of SPT heuristic,a new lower bound is provided with theoretical performance guarantees.Furthermore,numerical simulation method is also used to validate the effectiveness of the heuristic and the lower bound.(4)For the m-machine flow shop problem with total weighted completion time criterion,asymptotical optimality of SPT heuristic is proved.A lower bound is presented to deal with the problem for evaluating the performance of SPT heuristic.At the end,a series of numerical experiments are executed to show the effectiveness of the heuristic.(5)A blocking flow shop problem with total cubic completion time criterion is investigated using three kinds of intelligent optimization method,tabu search,simulated annealing and genetic algorithm.And a new neighbor structure is used in tabu search,which is better than other algorithms not only in time but also in the quality of solutions.(6)A new shop scheduling model is proposed for physical examination problem in medical management.In this model,each job is processed firstly in a flow shop and then in an open shop,to minimize the maximum completion time.For large-scale problems,the asymptotic optimality of the dense scheduling(DS)algorithm is proved in the sense of probability limit.Furthermore,a DS-based heuristic algorithm is presented to obtain approximate solution.For medium-scale,a discrete differential evolution(DDE)algorithm is provided to achieve high-quality solutions.A series of numerical simulations are executed to demonstrate the effectiveness of the proposed algorithms.