JIT系统中带学习效应和退化工件的平行机排序问题

论文摘要

本文研究在JIT系统中工件加工受学习和退化影响的共同工期指派和平行机排序问题,论文分别对极小化提前、延误和1工期的加权和问题（minimize∑（αEj+βTj+γd））与极小化提前费用、加权误工工件数与工期费用之和的问题（minimize∑f（Ej）+∑ejUj+g（d）,其中f、g分别是工件提前费用函数、工期费用函数）进行研究,目标是找到最优工期d*和最优排序π*,使目标函数f（d,π）最小.文章根据文献中的已有结论,先对问题的算法复杂性进行理论分析,然后为其特殊情况寻找多项式时间最优算法.首先,对于极小化提前与延误的加权和问题,本文分别研究了Pm|pj=（pj0+bsj）ra|∑（αEj+βTj）和Pm|pj=pj0raj+bsj|∑（αEj+βTj）,证明了分别存在时间复杂度为O（nm log n）和O（nm+2）的最优算法.其次,对于极小化提前和误工工件数加权和∑（αEj+ejUj）的问题,分别对之前两种实际加工时间模型进行研究,通过转化为指派问题均能在O（nm+3）时间内给出最优解.最后,对带退化工件和加工等级限制的问题Pm |pj=pj0+bjtj,GOS|∑ejUj+γd给出一个全多项式时间近似方案（FPT AS）,时间复杂度为O（n2m+2Lm+2/εm+1）.对各问题的扩展形式也分别给出了相应的结论.

论文目录

• 中文摘要
• Abstract
• 第一章 引言
•   1.1 研究背景及现状
•   1.2 假设和符号说明
• 第二章 极小化提前、延误和工期的加权和
• j=（p_j⁰+bs_j）r^a|∑（αE_j+βT_j+γd）'>  2.1 问题Pm|p_j=（p_j⁰+bs_j）r^a|∑（αE_j+βT_j+γd）
• j=p_j⁰r^a_j+bs_j|∑（αE_j+βT_j+γd）'>  2.2 问题Pm|p_j=p_j⁰r^a_j+bs_j|∑（αE_j+βT_j+γd）
•   2.3 算例
•   2.4 问题的扩展
• 第三章 极小化提前和误工工件数的加权和
• j⁰+bs_j）r^a|∑（αEvj+e_jU_j）'>  3.1 问题Pm|pj=（p_j⁰+bs_j）r^a|∑（αEvj+e_jU_j）
• j⁰r^a_j+bs_j|∑（αE_j+e_jU_j）'>  3.2 问题Pm|pj=p_j⁰r^a_j+bs_j|∑（αE_j+e_jU_j）
•   3.3 算例
•   3.4 问题的扩展
• 第四章 极小化加权误工工件数与工期费用之和
• j=p_j⁰+b_jt_j,GOS|∑e_jU_j+γd的转化'>  4.1 问题Pm|p_j=p_j⁰+b_jt_j,GOS|∑e_jU_j+γd的转化
•   4.2 算法及复杂性分析
•   4.3 问题的扩展
• 第五章 结论
•   5.1 主要结论
•   5.2 研究展望
• 参考文献
• 致谢

文章来源

类型: 硕士论文

作者: 岳娇

导师: 王海明

关键词: 学习效应,退化工件,共同工期指派,平行机排序

来源: 兰州大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 兰州大学

分类号: O223

总页数: 52

文件大小: 1539K

下载量: 27