Research On Some Bin Packing And Scheduling Problems In Supply Chain Management

This paper mainly studies a type of packing and scheduling problems in supply chain management,which have important applications in supply chain scheduling,plant location,and logistics distribution.This paper focuses on the two-customer processing and transportation coordination decision scheduling problem and extends it to multi-customer applications.The core of the research is the design of the approximation algorithm and the proof of the worstcase bounds,while the average performance of the algorithm is analyzed in conjunction with numerical experiments.The full text is as follows:Chapter 1 mainly introduces basic concepts about scheduling theory,the classical packing problem,and the current state of research on sorting problems with transportation,and expounds the sorting problem model that specifically needs to be studied in this paper.Chapter 2 presents a problem and algorithm for boxing items in two categories,which has important applications in scenarios where the items are separated because of factors such as the need for wet and dry separation,different chemical properties or susceptibility to corrosion and volatilization.In this problem,for a given set of items N={J1,J2,…,Jn} can be arbitrarily split into two mutually disjoint complete subsets N1={J1,J2,…,Jr} and N2={Jr+1,Jr+2,…,Jn}.Consider the relationship between the number of boxes obtained by the corresponding algorithm and the optimal number of boxes if the items in N1 and N2 are boxed separately and the items in N1 and N2 are boxed together.A DFFD algorithm is designed,the items in N1 and N2 are boxed separately using the FFD algorithm,and it is proved that the worst-case bound of the algorithm is 5/3 and the bound is tight.Chapter 3 investigates a type of scheduling problems with coordination decision making for processing and transportation of two-customer jobs.In this problem,for a given set of j obs N={J1,J2,…,Jn} all jobs need to be machined on a machine and transported by a vehicle and then delivered to two different customers.Each workpiece has a different processing time and physical size,the vehicles have a fixed on-board capacity and can be transported between customers,and the objective function is to minimize the maximum completion time Cmax,represented by the three-parameter method as 1→D,K=2|ν=1,c=z|Cmax.The best result for this problem is the 2-approximation algorithm published in EJOR in 2004,This chapter improves the problem by applying the DFFD algorithm from the previous chapter.Firstly,the worst-case bound proof of the algorithm in the original literature is improved and the new algorithm bound obtained is max{23/12,2-1/2α+1}(α≥1).Secondly,the improved algorithm for this problem is given and the worst-case bound of the improved algorithm is proved to be 23/12.Finally,by numerical experiments,the average performance of the algorithm is further demonstrated.Chapter 4 investigates a type of multi-client workpiece processing and transportation coordination decision scheduling problems.Extending the two-customer problem of Chapter 3 to the general case of any m customers,represented by the three-parameter method as 1→D,K=m|v=1,c=z|max.This chapter gives a heuristic algorithm for the problem based on the graph matching algorithm and the improved algorithm proposed in the previous chapter,and analyzes the feasibility and efficiency of the algorithm through numerical experiments.Chapter 5 summarizes the whole text,expounds the conclusion and analyzes the future research direction.