共查询到19条相似文献,搜索用时 78 毫秒
1.
研究了工件加工时间相同的确定单机调度最优交贷期和最优加工顺序的问题,且目标函数基于交货期和工件交货时间不准的情况。利用HLP不等式提出了时间复杂度为O(n^2)的最优算法。 相似文献
2.
讨论了带有交货期和工件的加工时间可控的单机排序问题.本文首先根据最优排序的性质确定了最优资源的分配方法,并将问题转化为指派问题,通过构造多项式时间算法确定最优排序.然后,本文将学习效应与加工时间可控问题结合,分别讨论了加工时间是线性资源函数和凸资源函数两种情况,证明了该类问题是多项式时间可解的.最后,讨论了一种特殊情况(学习因子是常数,加工时间是凸资源函数),给出了复杂性为O(nlogn)的算法,通过运行此算法确定最优资源分配量和工件的最优排序. 相似文献
3.
讨论n个独立工件在一台机器上加工,而且工件加工时间服从正态分布的交货期窗口设置问题,在等宽交货期窗口条件下,确定了工件交货期窗口,并证明这种交货期窗口设置只与窗口设置有关,而与工件排序无关。 相似文献
4.
5.
6.
每个工件依据其完成时间有一个满意程度.单机模糊交货期总加权满意程度最大化问题是一个NP-难问题.当工件的参数满足一定条件时,最优解中相邻工件的排列顺序也可以确定,从而简化问题的难度.本文对最优解的性质进行了分析和证明. 相似文献
7.
研究了一种具有模糊交货期的最小化全部满意度的单机调度问题。机器能力限制要求在任何时间至多加工一个工件,且在工件加工之间无空闲时间。考虑了一种梯形隶属度函数并推广为非线性情形。该问题清晰化后可利用动态规划状态空间松弛来求解。 相似文献
8.
讨论了带有交货期窗口和加工时间可控的单机排序问题。工件的加工时间是关于分配资源量的凸函数模型。工件若在交货期窗口前完工,则产生提前费用;若在交货期窗口后完工,则产生延误费用。分别研究了多窗口问题和单窗口问题。目标是在关于提前、延误、交货期窗口开始时间、交货期窗口大小和最大完工时间的函数约束条件下,确定工件的最优加工顺序、最优加工时间、极小化资源费用函数。通过将2个问题分别转化为指派问题,证明了2个问题是多项式时间可解的,问题的计算复杂性是O(n3)。 相似文献
9.
贾春福 《南开大学学报(自然科学版)》2003,36(2):93-97
完工时间与交货期偏差加权和最小化单机调度(简记TWD)问题是Just—In—Time生产环境下典型的调度模型,是NP—hard问题.然而工件权值与加工时间成正比时,LPT(Largest Processing Time)调度最优.本考虑了随机TWD问题,其中工件的加工时间和交货期都服从指数分布,证明了LEPT(Largest Expected Processing Time)调度的最优性,并进一步将结论推广到机器随机故障的情形. 相似文献
10.
讨论了带有交货期和工件的加工时间可控的单机排序问题。本文首先根据最优排序的性质确定了最优资源的分配方法,并将问题转化为指派问题,通过构造多项式时间算法确定最优排序。然后,本文将学习效应与加工时间可控问题结合,分别讨论了加工时间是线性资源函数和凸资源函数两种情况,证明了该类问题是多项式时间可解的。最后,讨论了一种特殊情况(学习因子是常数,加工时间是凸资源函数),给出了复杂性为O(nl ogn)的算法,通过运行此算法确定最优资源分配量和工件的最优排序。 相似文献
11.
研究了一种具有模糊交货期的平行机调度问题,目标函数是最大模糊延误修正值,并对相关的模型给出了算法。为了计算方便,文章采用模糊交货期的隶属函数与任务的完工时间之间的关系,判断任务是否误工。 相似文献
12.
IntroductionThere are many scheduling problems of practicalinterest in which the input data are uncertain or i mprecise,and this kind of uncertainty or i mprecision cannot bedescribed by probability theory.For these situations wherecharacteristics and constraints are neither deter ministic norprobabilistic,the problems may often be modeled withfuzzy sets.Fuzzy logic,which was introduced by Zadeh[1]hasbeen appliedto various industrial problems including productionsystems[2,3].Recently,there ha… 相似文献
13.
运用智能化算法解决具有模糊加工工期的单机器加工问题,需要一个计算效果的对比基准。本文基于MATLAB平台编制了相应的穷举法程序,并从穷举程序设计、枚举算法和界面设计等方面进行了探讨。最后,采用算例给出与遗传算法的比较结果。 相似文献
14.
讨论了具有学习效应的工期指派和可控加工时间的单机排序问题。工件的实际加工时间同时依赖于所排位置和所分配的资源消耗相关的函数,资源消耗分为线性和凸资源消耗2种。考虑共同工期、松弛工期和没有限制的工期3种工期分派方法。目标是确定工件最优的加工顺序、工期和资源分配量,极小化一个包含提前、延误、工期分派、总完工时间和总资源消耗的总费用函数。对于上述2种不同资源消耗函数与3种不同的工期分派方法的每一种组合,均给出了多项式时间算法。 相似文献
15.
本文考虑了一个包含工件生产和工件送货的单机调度问题。目标是寻找所有工件的公共交货期和每个工件的送货时间使得工件所受到惩罚(提前/拖后惩罚,送货费用等)的值最小。完成的工件按照批次进行送货,所有在公共交货期前完工的工件在最优交货期时间一起交付,对批次送货没有量的约束。本文确定了最优公共交货期,并给出了相应的排序。 相似文献
16.
A Genetic Algorithm for Single Machine Scheduling with Fuzzy Processing Time and Multiple Objectives
IntroductionMachineschedulinghasbeenoneoftheconsiderableresearchtopicsoverthelastdecades.BranchandBoundalgorithmsfordeterminingtheoptimalmakespanhavebeendevelopedandtestedonsmallsizedproblems.Inaddition,dispatchingrulebasedheuristicalgorithmshavebeenproposedinordertominimizespecificperformancecriteriasuchasflowtime,earliness/tardiness,makespanetc.Theschedulingproblemisknownasthen/m/p/cmaxproblem[1].Inthespecialcaseofm=1,theproblemisdescribedastheonemachineschedulingproblem.Manyresearchersdea… 相似文献
17.
讨论了安装时间和加工时间同时受资源约束的单机成组排序问题.目标函数为在满足最大完工时间限制条件下极小化安装时间消耗资源量与工件消耗资源量的总和.在讨论了问题若干性质基础上,给出了一个最优多项式算法,并用数值例子作了说明. 相似文献
18.
柏孟卓 《辽宁大学学报(自然科学版)》2001,28(4):313-317
讨论了任务到达时间依赖于分配给它的一类资源约束问题,对问题1|rj=fj(uj),∑^ujj=1≤U^A|Cmax,将已有的一个算法做了改进,对问题1|rj=fj(uj),Cmax≤C^A|∑uj给出了在任意给定排列的条件下求最优解的算法。 相似文献
19.
针对考虑工件投放期、交货期和机器准备时间的平行机问题,分别以最小化最大机器完工时间和最小化工件总延期惩罚费用为优化目标,建立相应的平行机问题模型,提出一种求解该问题的改进遗传算法。该算法中采用了基于工件和机器的多参数级联编码,染色体由工件子串和机器子串连接而成;提出了机器的加工能力、加工能力指数和冗余机器集的概念及相应的初始种群生成方法;对工件子串采用部分映射交叉,而对机器子串不作交叉运算;在变异算子中,提出基于机器负荷的启发式变异算子。 相似文献