Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery

This paper considers the integrated production and delivery scheduling on a serial batch machine,in which split is allowed in the delivery of the jobs.The objective is to minimize the makespan,i.e.,the maximum delivery completion time of the jobs.Lu et al.(Theor Comput Sci 572:50–57,2015)showed that this problem is strongly NP-hard,and presented a 32-approximation algorithm.In this paper,we present an improved 43-approximation algorithm for this problem.We also present a polynomial-time algorithm for the special case when all jobs have the identical weight.

硅锰炉自动配料系统

论述了配料系统的构成和工作流程,结合硅锰炉自动配料要求,设计了硅锰炉自动配料系统方案,搭建了硬件系统试验平台,利用VB编制了自动配料控制系统软件,重点研究了VB与PLC的串口通讯和PLC进行多仪表数据采集的串行通讯方法。试验结果表明:软件操作简单,串口通讯稳定可靠,提高了硅锰炉自动配料系统的自动化程度。

含串行批处理机的三阶段混合流水车间调度问题

基于钢铁行业炼钢-连铸-热轧一体化生产作业,提炼出新的三阶段混合流水车间调度问题。其中第二阶段有多台串行批处理机而其他阶段为离散机,批加工时间等于同一批内所有工件在第二阶段的加工时间之和,且考虑了设备需要调整时间等实际生产特征。以最小化总加权完成时间为目标函数,对该问题建立数学模型,提出基于工件分解策略的拉格朗日松弛算法,引入拉格朗日乘子将机器能力约束和批加工约束松弛到目标函数中,进而将形成的松弛问题分解为较易求解的多个工件级子问题,利用动态规划算法求解子问题,设计启发式算法将松弛问题的解转换为原问题的可行解。仿真实验表明,所设计的算法能够在可接受的运行时间内得到较好的近优解。

具有模具约束的单工序柔性继列型批调度问题研究

制造系统调度是调度问题研究的热点之一。相对于单件加工的调度问题研究来说,批量加工的调度问题研究较少。然而,批量加工较广泛存在于许多制造系统中,有其很强的工程背景。其中,注塑加工生产即是一种典型的批量加工生产方式。基于注塑加工生产的实际背景,提出了一种具有模具约束的柔性继列型批调度问题。针对此问题中所包含的三方面决策问题,研究了问题的求解框架;提出了启发式规则与遗传算法相结合的混合求解算法;设计了仿真调度案例并进行了仿真调度;通过对调度结果的详细分析,表明了调度结果的合理性和所提出算法的有效性。

目标为带权总完工时间的两排序问题随机化算法

研究了带权总完工时间的串行工件同时加工排序问题和自由作业问题。在证明问题NP困难的基础上,结合数学规划,分别设计随机化算法,并分析算法的性能比。

基于PLC的酿酒自动配料系统

自动配料系统既能提高配料生产的效率和配料精度,又能解放劳动力、极大的降低生产成本.设计了一种以PLC为核心控制器的酿酒自动配料系统.该系统通过工业以太网实现PLC与触摸屏通信实现人机交互,PLC通过485总线实现称重传感器的数据采集和上料电机的变频调速控制.系统具有配方加密设置、按配方自动配料、定量输出和实时远程监控等功能,实现了酿酒原料的快速、高精度的配料,具有很高的实用价值.

最小化时间表长的带有多个工件组有界继列批单机在线排序(英文)

在制造系统和半导体流水线上经常需要考虑的是在线继列分批问题.本文所考虑的问题中,每个工件具有各自的安装时间和加工时间(s,p),属于同一组的工件才能在同一批中加工,每一批最多可以加工b个工件,批的安装时间和加工时间分别为这一批中工件的最大安装时间和加工时间之和,目标函数是最小化工件的最大完工时间.利用对手法证明了任何一个在线算法的竞争比都不小于max{2b b+1,1+α},且给出了一个渐近意义下最好的竞争比是2的在线算法.

最小化时间表长的带有多个工件组单机无界继列批在线排序

考虑了批容量无界情形下带有多个工件组的单机继列分批的在线排序问题.每个工件具有各自的安装时间和加工时间(s,p),属于不同组的工件不能在同一批中加工,目标函数是最小化最大完工时间,给出了此问题的一个竞争比为2的最好可能的在线算法.

可控准备时间和加工时间的系列分批排序

在许多实际生产环境中,工件的加工时间不是固定不变的,由于工人或机器的工作时间较长,其加工工件的效率降低,使得实际的加工时间加长,也就产生了所谓的退化效应。为考察退化效应对工件排序的影响,讨论在退化效应的条件下,研究工件带有可控准备时间和可控加工时间的单机系列批排序问题。在退化效应的条件下,工件的加工时间为它的开始时间的递增函数;所有的工件从一开始就被划分为连续的批次,并在单机上分批进行加工;在每批工件加工前,都有一个依赖于开始时间的准备时间。目标是确定工件的排序,并将其划分成批,从而最小化最大完工时间和最大延误,并且给出最优算法来求解最小化最大完工时间和最大延误问题。

基于多路串行通信实现批量加载数据的方法

在基于需求分析和多路串行通信的基础上，给出了一种电子产品批量加载数据的智能化解决方案和构建模拟测试平台进行仿真测试的方法。方案应用C320 Turbo多路串行通信控制器和PC并口构建硬件系统，采用自定义加载通信协议和状态法的软件设计实现批量加载模块。测试结果表明：该方案有效地解决了加载请求自动识别、单包和多包数据批量自动加载等现实问题。所述方法是开发具有自主知识产权国产设备的关键。

到达时间与工期同序并带有不可用区间的串行批处理机问题

在制造业中,对串行批处理机的研究有重要的现实意义。考虑了机器带有不可用区间的单机串行批处理机问题。其中,工件的到达时间与工期是同序的。串行批处理机的容量为无限,工件带有2种不同的到达时间,分别为0或r,每批开始加工之前的安装时间固定且相同,在安装时间及不可用区间之内机器不能加工工件。批的加工时间为批内工件的加工时间之和,批的完工时间为批内最后一个工件加工完成的时间。同一批中工件的开始加工时间和完工时间分别相同,为该批的开始加工时间和完工时间。按时完工批按批EDD序排序。首先分析了问题的最优解性质,然后给出了动态规划算法并分析其时间复杂性,最后用数值例子验证了算法的正确性。

面向小批量定制产品的模块系列化设计方法研究

为了解决小批量定制产品在模块化过程中存在的模块配置不合理、部分模块重用率低且相似性高等问题,提出一种面向小批量定制产品的模块系列化设计方法.以惯性测试转台台面模块为例,研究了确定模块主参数及相关定义等内容,基于模块重用分析进行优先系列模块的初步选择,以优化客户需求满意度为目标对初选的优先系列模块进行优化,从而完成模块的系列化工作.最后选择9种模块(为总数的37%)作为优先系列模块,可以在保证加权直径差小于0.1的前提下兼容原有的24种模块.研究结果表明,模块系列化设计有效解决小批量定制产品模块化设计过程中现有的相关问题.

炼油行业废催化剂中重金属源释放特征及其影响因素

采用连续分批浸出和柱淋溶方法研究废催化剂中重金属在环境暴露下的源释放特征,其中连续分批浸出实验设置液固比为5∶1、10∶1和20∶1,浸提液pH值为4.5,柱淋溶实验浸提液为pH 4.5、pH 7.0及pH 7.0的浓度20 mg·L^(-1)的DOM溶液.结果表明,连续分批浸出中,酸性条件下废催化剂中重金属浸出率随液固比增大先上升后降低,液固比小时,浸出体系处于饱和状态,随着液固比增大,浸出体系逐渐变为非饱和状态,浸出率逐渐增加,但当液固比对废催化剂中重金属元素的浸出不起控制作用时,浸出率不受液固比影响.浸出机理受浸出体系饱和状态、重金属元素赋存状态和液固比多重控制作用影响;柱淋溶中,酸性条件促进了废催化剂中重金属元素的浸出,累积释放率增加,相较于中性条件,酸性条件下的平均浸出率增加了13.4%,酸性条件未改变废催化剂中重金属元素的释放机理;溶解性有机质条件促进了废催化剂中重金属元素的浸出,累积释放率显著增加,相较于中性条件,溶解性有机质条件下的平均浸出率增加了19.6%,溶解性有机质条件未改变废催化剂中重金属元素的释放机理;连续分批浸出中最大重金属释放率均高于柱淋溶中的最大重金属释放率,且连续分批浸出中重金属浸出机理更易受外界条件影响,环境风险更大.因此在废催化剂的堆存、运输和处置过程中应注意避雨、防渗、隔离等措施,避免废催化剂中的重金属向地表水、地下水和土壤等环境介质中转移,造成更大的环境损害.

一类串行工件同时加工排序问题的研究

研究目标为带权总完工时间的串行工件同时加工排序问题,证明该问题在分批数固定时的NP困难性,并基于数学规划提出随机化算法。最后,对特殊分批进行了讨论。

最小化时间表长和最大加工运输时间的单机继列批在线排序

研究了目标函数为时间表长和最大加工运输时间的单机继列批在线排序问题.对于时间表长问题,给出了当批容量无界时竞争比是5～(1/2)+1/2的最好可能的在线算法和当批容量有限时竞争比不超过2的在线算法;对于最大加工运输时间问题,证明了当批容量无界时的竞争比不超过2.

到达时间与工期同序的串行批处理机排序问题

笔者考虑的工件带有到达时间,且到达时间与工期同序、目标函数为加权误工工件数的单台串行批处理机排序问题是NP-难的,其中批处理机的容量无限。当同一批中的工件都到达后,此批才可以开始加工。同一批中工件的开始加工时间相同,批的加工时间为此批中所有工件的加工时间之和,且完工时间也相同,为这批中最后一个工件的完工时间;每批开始加工之前都有一个固定的调整时间,而批内工件间无调整时间,在批的调整时间内机器不能加工任何工件。研究工件带有2个不同到达时间,且到达时间与工期同序的情况。对于目标函数为加权误工工件数问题,分析了其最优解的性质,给出了拟多项式动态规划算法及其时间复杂性。

自动定量装车系统在胜利油库的应用

胜利油田新建油库的发油装车过程通过美国PYRAGON批量控制器来实现。定量装车是安全发油、计量、结算的关键。本文从油库系统架构入手,介绍了定量装车的原理、流程及通讯技术的实现。

一台串行批处理机上的一类有主次指标的排序问题

考虑一类带机器安装时间的单机双目标串行分批排序问题.对这样两个问题1,s|s-batch,B≥n,Cmax≤u|∑Cj和1,s|s-batch,B≥n,∑Cj≤v|Cmax,通过动态规划给出了多项式时间最优算法.

加工时间线性递减的平行机排序问题

主要讨论了具有两台处理机的平行机排序问题和每批恰为k个工件的串行工件同时加工排序的平行机排序问题。在这两个问题中,工件加工时间均为开工时间的线性递减函数,目标函数为极小化总完工时间。对于第一个问题,证明了其最优排序可由工件按基本加工时间不减排列得到,由此得出其最优算法,并指出了该结论对于加工时间随开工时间线性递增的情况并不成立。对于第二个问题,根据其与第一个问题在某些性质上的相似性,给出了其最优算法。最后指出所讨论的两个问题的结论均可推广到m台处理机的情况。

线性退化且有独立安装时间的单机系列批排序

讨论了任务带有基本加工时间和线性退化且每个批都有独立安装时间的单机系列批排序问题。每个任务的基本加工时间都不相同,但是它们都有相同的退化率。任务实际的加工时间可以描述成关于其基加本工时间与开始时间的一次线性函数,即Pi=bi+at,这里bi和a分别为任务Ji的基本加工时间和退化率,t则为任务Ji的开始时间。目标是确定批的个数及批内的任务排序,从而极小化最大完工时间。首先,所有的任务在加工之前先被划分成一系列的批;然后,在单机上分批加工,每批在被加工之前都有一个独立的常数安装时间s;最后,在R-FBLDR算法的基础上进行了修改,得到了极小化最大完工时间的最优算法,该算法的时间复杂性为O(nlogn),其中n为任务个数。