冷链中的订单排序问题研究

发布时间：2018-03-02 05:32

本文关键词： 冷链投送期流水作业订单排序近似算法　出处：《鲁东大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着社会的迅速发展,人们对物质生活的追求也随之提高,他们对食物也有了更高的要求,特别是对冷鲜的肉食.由于人们对食品安全和营养价值的较高追求,他们会更倾向于购买大型企业生产的品牌产品.为此,企业决策者们为了招揽更多的客户,希望通过采取一些措施达到既降低成本又能提高服务质量.但是,在实际的冷链加工业中,二者很难同时实现,由此会产生一些不好的效果,如:缺货率高,配送延误,产品品质降低等,从而会使市场额下降.在此背景下,冷链加工业中的排序问题引起了学者们的广泛关注.如何既能满足不同客户的特殊需要又能使企业的损失达到最小,找到一个行之有效的方法,能够快速的协同安排生产和配送是即将要解决的问题.本文考虑的是几类基于冷链加工的订单排序模型.对于不同的机器环境和目标函数设计了近似算法.本文的主要内容如下:1.针对有固定投送期与存储费用的单机环境下的订单排序模型,考虑的问题是极小化工件最大完工时间和存储费用的加权和这一问题.利用3-划分证明了问题的一般情形是强NP-困难的,并证明没有固定近似比的多项式时间的算法.对于投送期呈周期性这一特殊情形,提出了一个3/2-近似的算法,同时证明了该近似比是最好的,除非P=NP.2.针对有就绪时间的流水作业(flowshop)订单排序模型,研究了极小化时间表长(makespan)问题.文章将订单进行了分批考虑,对于订单有固定就绪时间的情形,利用2-划分证明了问题是一般NP-困难的.提出了一个伪多项式时间的动态规划算法,并根据改善的Johnson规则设计了2-近似的算法.针对问题的特殊情形,基于Johnson规则,提出了2-近似算法并进一步改进算法,设计了3/2-近似的算法.最后考虑了一个批有固定数目的情形,并设计了一个简单的算法.
[Abstract]:With the rapid development of society, the pursuit of material life is increased, they also have higher demand for food, especially for cold fresh. Because the people of carnivorous higher food safety and nutritional value of the pursuit, they will be more inclined to buy large enterprises producing brand products. Therefore, the enterprise decision researchers in order to attract more customers, hopes to take some measures to reduce the cost and improve the quality of service. However, in the cold chain industry practice, the two is difficult to realized at the same time, it will produce some bad effects, such as: high rate of out of stock, delivery delays, reduce product quality, thus the market volume decreased. Under this background, the sort of cold chain in processing industry has aroused wide attention from scholars. How to meet the special needs of different customers and can make the enterprise loss minimum, find a The effective method to quickly arrange the production and distribution of cooperation is going to solve the problem. This paper is concerned with several models of order scheduling based on cold chain processing. For different machine environment and design target function approximation algorithm. The main contents of this paper are as follows: 1. according to a fixed order scheduling model of delivery and storage period the cost of a single machine environment, consider the problem is minimizing the maximum completion time and storage cost and weighted the problem. By using the 3- division shows that the general problem is strongly NP- hard, and prove that there is no fixed polynomial time approximate ratio algorithm. For a special case of the delivery period periodically, propose a 3/2- approximation algorithm, and proves that the approximation ratio is the best, unless P=NP.2. for ready time line (flowshop) ordering model, research To minimize makespan (makespan). The order of partial consideration, a fixed ready time in the case of orders, using 2- division shows that the problem is generally difficult. NP- proposed a dynamic programming algorithm for pseudo polynomial time, and the design of the 2- approximation algorithm based on improved Johnson special case rules. In order to solve the problem, based on the rules of Johnson, put forward 2- algorithm and improved algorithm, 3/2- approximation algorithm design. Finally we consider a number of fixed number of cases, and a simple algorithm design.

【学位授予单位】：鲁东大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223

【相似文献】