【摘 要】
：
在实际生产过程中，机器并不是不间断地在工作.机器维修、机器定期检查等因素使得机器的可用性受到限制.本学位论文考虑的机器可用性限制指的是：机器上有一个禁用区间.工件带有
论文部分内容阅读
在实际生产过程中，机器并不是不间断地在工作.机器维修、机器定期检查等因素使得机器的可用性受到限制.本学位论文考虑的机器可用性限制指的是：机器上有一个禁用区间.工件带有位置限制指的是每个工件都必须在它被指定的位置之前在机器上进行加工.本文综合考虑了以上两个因素，并研究机器具有可用性限制并且工件具有位置限制的若干单机排序问题. 本文研究的内容主要分为两部分.第一部分研究可中断情形下单台机器带有一个禁用区间[R,D]并且每个工件都有位置限制的排序模型.第二部分研究不可中断情形下单台机器带有一个禁用区间[R,D]并且每个工件都有位置限制的排序模型. 我们用h1表示机器上只有一个禁用区间的限制，用σ[Jj]≤kj表示工件Jj必须在前 kj个位置在机器上进行加工的限制. 在第二章，我们所研究的排序问题有： ?工件可中断最小化最大延迟排序问题1，h1|σ[Jj]≤kj,pmtn|Lmax. ?工件可中断最小化完工时间和排序问题1,h1|σ[Jj]≤kj,pmtn|∑Cj. ?工件可中断最小化最大费用排序问题1，h1|σ[Jj]≤kj,pmtn|fmax. 针对以上三个问题，我们分别给出了多项式时间算法. 在第三章，我们所研究的排序问题有： ?工件不可中断最小化完工时间和排序问题1,h1|σ[Jj]≤kj,|∑Cj. 针对上述问题，在第3.2节，我们给出了一个2-近似算法.在第3.3节，我们证明了，如果对某些工件的长度加以限制，则存在一个20/17-近似算法.在第3.4节，在与第3.3节相同的限制条件下，我们给出了一个多项式时间近似方案（PTAS).
其他文献
干部选拔制度创新是干部选拔工作从思想观念、工作方法到管理体制和运行机制的全面创新,是一场深刻的人事制度改革。实现干部选拔制度的创新,应从以下几个方面去努力:创新干
德育教育是小学阶段素质教育的重要组成,有助于完善学生的心理品质,促进学生身心健康发展.小学体育教学同样在学生身心发展当中有着重要作用,将体育和德育教育进行融合与小学
在这篇论文中,我们首先在紧致带边Hermitian流形上解决了Higgs-Hermitian-Einstein方程的Dirichlet问题.进一步,我们得到了一类完备非紧Hermitian流形上Higgs丛的Hermitian-Einstein度量的存在性结果.
本文在代数曲线奇点和拐点的数值计算算法的基础上,借助于八叉树数据结构和区间运算技术,提出了计算代数曲面奇点的一种新的数值计算算法.该算法保证能将任意次数的代数曲面
根据原有ZYDC3000/28/47型运输顺槽超前支架的结构特点、与运输顺槽的配套性,进行了超前支架的改进设计,将底座改进为可伸缩式,降低了支架的运输高度。现场应用表明,改进后的
在采用泛函分析方法求解积分--微分方程时,谱分析是构造方程解的核心和疑难问题.本文研究了迁移理论中的一些问题,具体说来有:讨论了具有零进入边界条件迁移模型的谱映射定理
伴随着中等职业的教学越来越被重视,全国各地的中职学校都在响应号召,积极推广理实一体化教学.本文想要阐述的是烹饪专业的理实一体化教学,主要结合烹饪教学的独特点,浅谈了
凸极小化问题是优化领域中比较重要的一类问题,而几乎所有的凸优化问题都可以转化为一个光滑函数f与一个非光滑函数g之和的极小化问题,对于解决此类问题的己知方法中,一个重
Koszul代数最早由Priddy于1970年首次引入，它是一类具有很多良好同调性质的且与半单代数很接近的一类二次代数.很多重要的代数都是Koszul代数，如路代数，张量代数，多项式代数，Steen