Study On Production Scheduling Problem Based On Constraint Programming With Resource Re-allocation

In the 21 st century,advances in technology,globalizing economics and the rapid changing of market environment make manufacturing process become increasingly complex.Traditional mass production mode gradually changes to the mode to produce more customized goods with smaller sizes.In order to meet customized demands,production scheduling,one of the core problems manufacturing enterprises have to resolve,is becoming increasingly complex and difficult.Based on a testing process of semiconductor chips which need to pass through several steps to finish the testing,this paper studies how to deploy several types of testing resources among different processing steps to maximize the number of chips that pass through all the testing process steps.The problem is very complex due to the following considerations:(1)each step requires different combination of types of resources;(2)each kind of resources is limited and shared among all processing steps;(3)changing the resources to meet the resource specification requirement in each step takes time;and(4)the changing time is different,dependent on the type of resources that need to be changed.This paper built a nonlinear programming model for the problem.Defining as the decision variable whether the machine is staying at a process step at a particular time period,we can analyze the dynamic changes of the machine status along the whole planning horizon.Since the machines' statuses between two consecutive time periods are interactive,the solution structure is complex and solving the mathematical model is relatively difficult.Based on the depth-first search rules,we propose a method which combines the constraint propagation method and the domain search.The domain search is embedded into each execution of the constraint propagation.This constraint programming-based method mainly includes two steps: the first step is to confine the solution space by checking the consistency of the problems,and the second step is to delete unpromising branches by introducing enhanced consistency checking conditions based on some theoretical and simulation analysis.Numerical results show that:(1)For small and medium-scale problems,the proposed method is able to obtain the optimal solution in a reasonable amount of time while takes a long time for large-scale problems;(2)For large-scale problems,theproposed method incorporating with the checking of whether the production system has achieved an equilibrium status can produce near-optimal solutions within a reasonable amount of time.