The Research On Order Scheduling In Cold Chain

With the development of society,the demand for food is higher and higher,especially for the cold meat.People will be more inclined to buy large-scale production of brand products for the high pursuit of food quality.Therefore,in order to attract more customers,business decision-makers expect to take some measures to achieve the aim of the both lowcost and high service quality.However,the two are difficult to achieve at the same time in the actual cold chain processing industry,which will lead to some bad results,such as: high rate of out of stock,delivery delays,low product quality,etc.,which will make the market decline.Based on this context,the cold chain processing industry in the sorting problem has aroused the concern of scholar.How to meet the special needs of different customers and minimize the loss of enterprises at the same time,and find an effective way to collaborate on the production and distribution quickly is a problem to be solved.Several kinds of order scheduling models based on cold chain processing are considered in this paper.The corresponding approximation algorithms are designed for different machine environments and objective functions.The main contents are summarized as follows:1.For a single machine order scheduling with inventory constrained and fixed delivery dates,the minimize the weighted sums of makespan and the holding cost is considered.By using the 3-partition problem,it is proved that the general version of our problem is strongly NP-hard,and polynomial time approximation algorithm with a fixed performance ratio is not exist.For the special case of the period delivery dates,a polynomial 3/2 approximation algorithm is proposed.This result is the best possible unless P=NP.2.For the order scheduling in a flowshop with release dates,the problem of minimizing the makespan is considered.First,the orders are considered in batches.By using the 2-partition problem,it is proved that the problem is NP-hard for the orders with a fixed number of release dates.A pseudo-polynomial-time algorithm for the problem is presented,and 2 approximation algorithm is proposed based on modified Johnson's rule.Similarly,for the special case of the problem,the 2 approximation algorithm is designed and is modified into 3/2 approximation algorithm based onJohnson's rule.Finally,the case of the batches of a fixed is considered and a simple algorithm is presented.