Economic Batch Scheduling Model With Material Order And Product Delivery Consideration

To reduce the purchasing cost and delivery cost, material ordering and final product delivery are organized by batch in many manufacturing companies. The interaction among ordering batch, job sequencing and delivery batch result in a very complex batch scheduling problem. The thesis studies this problem on problem complexity, mathematical model and efficient optimization algorithms.Firstly, the problem complexity is studied. Based on the proof of NP-hardness, two polynomial time solvable special cases are proposed: one of which one consider the ordering batch and job sequencing, and the computational complexity is n2; the other consider the situation that the job sequencing is given, and also has the computational complexity of n2. the two special cases provide insights for the optimization algorithms.Secondly, a mixed integer programming is built, and CPLEX is employed to solve the model.At last, efficient optimization algorithms including a branch and bound algorithm and 3 heuristics are design. In the branch and bound algorithm, lower bounds and dominate rules are researched to improve the efficiency, and the 3 heuristics make the scheduling decision in 3 different ways. Computation experiments show that branch and bound algorithm performs better than CPLEX for small scale instances, and heuristics can solve the large scale instances with the gap to lower bound less than 13%.With the study in this thesis, the batch scheduling problem is established, and efficient algorithm would help company to make better batch scheduling decision to reduce purchasing and delivery cost.