Single-Machine Production Plan And Batch Delivery In Supply Chain Scheduling

Scheduling problem is one of the classical combinatorial optimization problems. It studies how to allocate and schedule the scarce resources reasonably to obtain the maximization profit. It is widely used in the real production environment. An efficient scheduling solution can improve the utilization rate of production equipment, reduce the cost, and increase the company’s profit. The supply chain scheduling problem is an extension of the production scheduling problem, which studies jointly or coordinated scheduling problems through supply chain. The supply chain includes suppliers, manufacturer, distributors and third party logistics. By information sharing and cooperation among members, the joint scheduling models of the whole system are developed, which can not only improve customer service level, shorten the lead time, but also lower the operations cost of the entire supply chain. It has important research value to the Manufacture area. Firstly, we summarize the research background and significance of the supply chain scheduling and introduce the research status in detail.Secondly, we review the fundamental theories which include the combinatorial optimization problem, scheduling problem, the related algorithms and computational complexity. Also, we give an outline of the solution method of scheduling problem and the full polynomial-time algorithms scheme (FPTAS) we used.Thirdly, batch delivery supply chain scheduling models are studied. We first analysis the complexity of the general problem and prove it strongly NP-hard. Then the problem becomes NP-hard in the ordinary sense when the number of batches B satisfies B≤U for any constant U≥2and we present an FPTAS for this case. Furthermore, we study three polynomial time solvable models and design the corresponding polynomial time optimal algorithm to each model. According to the calculation examples, they proved the effectiveness of the algorithms.Fourthly, supply chain scheduling with deteriorating effect model are studied. Similarly, we first analysis the complexity of the general problem and prove it strongly NP-hard. Then, we also prove that there is no polynomial-time approximation algorithm with a constant upper bound for this case unless P=NP. For the case with a given number of batch arrivals, we analysis the complexity of it, then prove it still strong NP-hard problem and present an FPTAS to solve it. Finally, by analyzing the experimental examples of the FPTAS for the two models in Chapter III and Chapter IV with MATLAB, we finally find the optimal batch number and the optimal job sequence in each batch so that the total cost are minimized.