| As the pillar industry in China,manufacturing developed rapidly in nearly three decades,but there are many problems appeared in the market at the same time.The modern world is experiencing rapid development of information technique,on the one hand,a new product is difficult to counterfeit and the life cycle become shorter and shorter.So,to maintain competitiveness in market,enterprises must speed up the production process.According to the empirical data,nearly 85%of the makespan has cost in waiting and transportation.So making an effective scheduling strategy is crucial to optimize the production process.On the other hand,The diversification of customers’ needs makes production more difficult.And the production mode of vertical integration will inevitably lead to waste of resources and rising costs.So,many companies choose outsourcing as a valid way to expand internal capacity.In this context,we establish a reasonable production scheduling model and design optimization algorithm for it,which is of great significance from the angle of theoretical research and reality.The first part of the paper introduce the background and the implications for research on production scheduling.Then it summarizes some hot topics and research methods of production scheduling in some relevant literature.Secondly,the paper studies the problem of production scheduling with job outsourced.Considered about enterprise’s interior producers’ factors,this paper puts forward two unified scheduling models which the job processing time depends on position.For the first time,these two models have integrated learning effects and aging effects into a same model.Then,based on the above two models,the paper puts forward another two unified scheduling models with outsourcing allowed,which are called choosing one vendor model and choosing many vendor model.The first one applies to small and medium enterprise,they always choose to cooperate with one fixed outsourcer to reduce costs efficiently and gain economies of scale.The second model applies to large enterprises.The large enterprises will at the risk of the leakage of assets specialty and knowledge when they cooperate with single outsourcer,so they’d like to work with more outsourcers.Next,we did some research at the environment of parallel processing,try to minimize the makespan and the cost of the outsourced jobs,we also try to solve the problem of minimize the total completion times and the cost of the outsourced jobs.For each problem,the scheduling policy decision includes the choose of outsourced jobs,the scheduling scheme of outsourcing production and the scheduling scheme of in-house production.We first analyze the complexity of each problem.Then we set forth corresponding polynomial-time optimal algorithms for the polynomial-time solvable problems.For the NP-hard problems,we propose a fully polynomial time approximation scheme(FPTAS)and then prove the approximation and feasibility of the algorithm.Finally,we use MATLAB to analyze the FPTAS and the polynomial-time optimal algorithms with some experiment,and verify the feasibility and effectiveness of the approximation algorithm from the angle of practice. |
