Batch-Processing Scheduling with Setup Times

The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch. The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time.     

一类新型批处理机调度问题的理论分析

钢卷在冷轧生产中,为了改进其性能,需要在罩式炉进行退火,退火过程由加热、保温和降温三段组成,而这三段处理时间由于工艺上的要求不能归结为一个时间,这与传统批处理机调度有明显的差别.对新型批处理机的总加权完成时间最小化问题建立了非线性整数规划模型,开发了基于动态规划的启发式算法.通过理论分析,获得该算法的误差性能比为3.对于三段中的某一段板卷的处理时间相同的情况,证明了启发式算法的误差性能比是2,而且证明是紧界.对于三段中的某二段板卷的处理时间相同的情况,证明了启发式算法是最优算法.对启发式算法扩展到带有任意段的加工时间的一般情况进行了性能分析.     

Order batching in a pick-and-pass warehousing system with group genetic algorithm

An order batching policy determines how orders are combined to form batches. Previous studies on order batching policy focused primarily on classic manual warehouses, and its effect on pick-and-pass systems has rarely been discussed. Pick-and-pass systems, a commonly used warehousing installation for small to medium-sized items, play a key role in managing a supply chain efficiently because the fast delivery of small and frequent inventory orders has become a crucial trading practice because of the rise of e-commerce and e-business. This paper proposes an order batching approach based on a group genetic algorithm to balance the workload of each picking zone and minimize the number of batches in a pick-and-pass system in an effort to improve system performance. A simulation model based on FlexSim is used to implement the proposed heuristic algorithm, and compare the throughput for different order batching policies. The results reveal that the proposed heuristic policy outperforms existing order batching policies in a pick-and-pass system.     

钢筋代换对钢筋配料长度的影响分析

建筑工程和水利工程钢筋配料计算都要考虑钢筋弯曲情况下的长度增加与弯折情况下的长度减少，而施工中较为普遍的钢筋代换往往导致钢筋弯曲位置改变，导致按原先配料长度进行施工出现偏差.文章对钢筋代换进行分析并运用到钢筋配料计算中，对代换前后钢筋长度进行计算、对比和分析并得出结论，以期为钢筋代换后的施工配料提供指导.     

Optimal Allocation of Effort to Software Maintenance: A Queuing Theory Approach

We develop variations of the M|G|1 queue to model the process of software maintenance within organizations and use these models to compute the optimal allocation of resources to software maintenance. User requests are assumed to arrive following a Poisson process and a binomial distribution is used to model duplication of requests. We obtain expressions for expected queue lengths with an exponential server using an N‐policy for an integer N≥1. We also obtain the optimal batching size and mean service rate by minimizing the total cost consisting of the cost of the server, the cost of waiting, and the fixed cost of maintenance, if applicable.     

基于JIT装配模式的网上超市订单分拣优化模型

订单分拣是大型网上超市生存和发展的关键环节，如何在数百万种商品中将订单要求的商品高效、准确地进行拣选并包装，是亟待解决的难题。本文以提高大型网上超市订单分拣方法的科学性为目标，针对订单拣选、集货复核、包装这一作业流程，基于JIT装配流水线思想，建立大型网上超市订单成组分拣的优化模型与求解方法。在构建订单分拣流程中各工序作业时间计算模型的基础上，建立了订单分批与排序的联合优化模型。围绕缩减求解空间的思想提出两阶段启发式优化方法。通过应用实例分析和灵敏度分析证明了算法的有效性。结果表明，本文提出的网上超市订单成组分拣方法相较于传统方法可较大幅度提高订单分拣的效率，为网上零售企业的订单拣选和包装作业流程的优化提供了理论指导。     

考虑完成期限的电子商务在线订单分批模型及算法

在电子商务在线订单拣选系统中,订单到达时间和订购商品等信息未知。针对拣选设备容量、员工人数等资源有限约束情况,研究在何时、对多少订单进行分批优化,以保证在订单完成期限前以最短的时间拣出最多的订单。构建考虑订单完成期限的在线订单分批混合整数规划模型,以最小化平均有效订单服务时间,采用改进的固定时间窗订单分批启发式规则求解模型,定义剩余操作时间在[前置时间,配送准备时间]内的订单为紧急订单,构建综合考虑紧急程度和相似度因素的在线订单分批算法。采用某配送中心14：00～18：00时间段内以泊松分布（λ＝17）随机生成的订单进行数据实验,将实验结果与传统固定时间窗在线订单分批算法进行比较。研究结果表明,考虑完成期限时,系统拣选配送的订单数量更多,总服务时间和平均有效订单服务时间更短,且出现延迟订单的数量更少,延迟时间更短。拣选员工人数的增多在不同程度上提高配送率,且考虑完成期限时,配送率提高幅度要大于传统算法;但随着人数的增加,配送率的提高幅度呈降低趋势。     

极小化最大完工时间的批到达同时加工排序问题

考虑工件成批到达的同时加工排序问题,目标函数为极小化最大完工时间.给出模型在特殊情况下的统筹算法和针对一般情况的局部统筹算法,并通过大量的实例计算来验证两启发式方法的有效性.     

Scheduling a single semi-continuous batching machine

This paper addresses a new problem, called semi-continuous batch scheduling, which arises in the heating-operation of tube-billets in the steel industry. Each heating furnace can be regarded as a semi-continuous batching machine, which can handle up to C jobs simultaneously. The jobs in the same batch enter and leave the machine semi-continuously, which differs from the traditional batching machine scheduling where the jobs in same batch have a starting time and a finishing time. In this paper the processing time of a batch depends on the capacity of the semi-continuous batching machine, the longest processing time of jobs in the batch and its size. The objectives are to schedule jobs on the machine so that the makespan and the total completion time are minimized. A schedule for a semi-continuous batching machine consists of a batching and sequencing for the batches. We propose the optimal properties of two different objective functions and present the different dynamic programming algorithms with a running time of O(n²), respectively.