随着社会的迅速发展,人们对物质生活的追求也随之提高,他们对食物也有了更高的要求,特别是对冷鲜的肉食.由于人们对食品安全和营养价值的较高追求,他们会更倾向于购买大型企业生产的品牌产品.为此,企业决策者们为了招揽更多的客户,希望通过采取一些措施达到既降低成本又能提高服务质量.但是,在实际的冷链加工业中,二者很难同时实现,由此会产生一些不好的效果,如:缺货率高,配送延误,产品品质降低等,从而会使市场额下降.在此背景下,冷链加工业中的排序问题引起了学者们的广泛关注.如何既能满足不同客户的特殊需要又能使企业的损失达到最小,找到一个行之有效的方法,能够快速的协同安排生产和配送是即将要解决的问题.本文考虑的是几类基于冷链加工的订单排序模型.对于不同的机器环境和目标函数设计了近似算法.本文的主要内容如下:1.针对有固定投送期与存储费用的单机环境下的订单排序模型,考虑的问题是极小化工件最大完工时间和存储费用的加权和这一问题.利用3-划分证明了问题的一般情形是强NP-困难的,并证明没有固定近似比的多项式时间的算法.对于投送期呈周期性这一特殊情形,提出了一个3/2-近似的算法,同时证明了该近似比是最好的,除非P=NP.2.针对有就绪时间的流水作业(flowshop)订单排序模型,研究了极小化时间表长(makespan)问题.文章将订单进行了分批考虑,对于订单有固定就绪时间的情形,利用2-划分证明了问题是一般NP-困难的.提出了一个伪多项式时间的动态规划算法,并根据改善的Johnson规则设计了2-近似的算法.针对问题的特殊情形,基于Johnson规则,提出了2-近似算法并进一步改进算法,设计了3/2-近似的算法.最后考虑了一个批有固定数目的情形,并设计了一个简单的算法.