Column Generation-based Algorithms For Lot-sizing And Scheduling With Sequence-dependent Setup

With the development of 5G communication technology and artificial intelligence,the demand of semiconductor chips are soaring in both civilian and utility sectors,which requires more efficient semiconductor manufacturing systems.Along with hard constraints and delicate production process,the complexity of semiconductor manufacturing system is widely recognized among the academic and industrial community.As bottleneck sites are key parts in the production system,this thesis focuses on multiple bottleneck sites in the semiconductor assembly and test manufacturing,and models it as the capacitated lot-sizing and non-identical machine scheduling problem with sequence-dependent setup time,the carryover of setup state,and backlog.Two new mixed integer programming models are proposed,including the simplified facility location(SFL)model and the simplified shortest path(SSP)model,followed by exploring their relative efficiency in obtaining optimal solutions and linear relaxation lower bounds.Due to the existence of sequence-dependent setup time,it is hard to decompose the original problem into multiple single-item lot-sizing sub-problems.At the same time,it is difficult to decompose the original problem into multiple single-period lot-sizing problems on account of the carryover of setup state.We therefore propose the per-machine Danzig Wolfe decomposition as well as its Lagrangian relaxation problem.We prove their equivalence analytically.Besides,in order to handle the degeneracy problem,a notorious problem possibly encountered in the column generation,the sub-gradient optimization algorithm is invoked once a degeneracy problem occurs.Furthermore,we observe an obvious correlation between the optimal solutions and two lower bounds including the linear relaxation solutions,and the pricing sub-problem solutions of the Danzig Wolfe decomposition by statistical analysis.We then build a statistical estimation model(i.e.,a generalized linear model)to give insight on the optimal values,especially about information regarding whether or not the setup state variables in the optimal solution take the value of 1.The relative~2 values among the predictions,training data and testing data are high,indicating an acceptable modeling accuracy and prediction capability for testing data.Last but not least,the probabilistic information from the statistical evaluation model is further used in the branching and selection procedure,with the aim to improve the solution quality.Extensive numerical experiments are conducted and the results show that the average difference between the solutions obtained by the algorithm and the optimal solutions is less than 1%for small-scale problems,and the algorithm performs better than the relax and fix algorithm for all-size tested problems.