两类极小化最大加权完工时间排序问题研究

研究两个单机排序问题,目标函数均是最大加权完工时间。对于问题1‖maxwjcj,证明了LW规则序是最优排序,而问题1|rj|maxwjcj,用3-划分问题归结,证明是强NP困难的。

最小化最大加权完工时间重新排序研究

重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个合理的排序.本文研究最大加权完工时间的重新排序问题,问题的目标是:1)在原始排序错位限制的条件下最小化最大加权完工时间;2)最小化最大加权完工时间与原始排序的错位的加权和.在本文研究中我们假设所有工件在0时刻到达.文章的主要结果:对于Γ∈{D_(max)(π~*),△_(max)(π~*)},给出了问题1|Γ≤k|max w_jC_j和问题1‖maxw_jC_j+μΓ多项式时间的求解算法;证明了问题1|∑△_j(π~*)≤k|max w_jC_j和问题1‖max w_jC_j+μ∑△_j(π~*)是强NP-困难的.

考虑退化效应的钢箱梁小节段在线生产调度研究

钢箱梁小节段作为桥梁组装的基础构件,需求量非常大,其生产方案的优化对制造商有着很大的影响,针对钢箱梁小节段的在线生产调度研究就显得愈发迫切与重要。本文研究工件具有退化效应的钢箱梁小节段单机在线生产问题,建立了的两个不同的退化加工模型,以最小化最大加权完工时间为优化目标。首先,对所研究的两个问题,都证明了最优排序应具有的性质。然后,对加工时长模型为pj=αjt(t>0)的问题,给出了一个竞争比为1+αmax最好可能的在线算法,其中αj为工件Jj的退化因子;同样,对加工时长模型为pj=αj(A+Bt)(A>0)的问题,也给出了一个竞争比为2+Bαmax最好可能的在线算法。最后,对文中的两个在线模型都进行了数据模拟,验证了在线算法的有效性与正确性,也为制造商的生产管理提供了有效参考。