公共工期排序问题的分枝定界算法

本文着重对以极小化延误损失为目标的公共工期单机排序问题 1|d|ΣWiTi 进行了研究 .根据该问题的性质 ,我们设计一个分枝定界算法 .

具有多重公共工期的单机退化工件排序

研究了需要同时确定最优工件工期和加工序列的单机排序问题。工件的加工时间是其开工时间的线性增长函数。每个工件的惩罚费用包含两部分,一部分是分配给它的工期费用,另一部分是由机器上产生的提前及延迟惩罚费用。管理者的目标为最小化所有工件的总惩罚费用。对于公共工期个数固定的情形,给出了一个多项式时间算法。

公共工期指派和可控处理时间资源约束下最大费用最小化单机排序问题

本文研究具有公共工期指派的凸资源单机排序问题。任务的实际加工时间是所获得的资源量的凸函数,目标函数是所有任务费用中的最大值。考虑两个问题。在第一个问题中,假设可用资源总数量有限,决策者需要寻找任务的最优排序、公共工期和资源分配方案,使得最大费用最小。第二个问题与第一个问题互补,资源总量没有限制,目标是在最大费用有上界限制条件下,求出最小资源总量、任务排序和公共工期及资源分配方案,使得资源总量最小。分别将上述问题转化为非线性凸规划问题加以处理。证明了两个问题均可以在多项式时间内求出最优解,提供了求解上述问题的多项式时间最优算法。分别给出实例说明算法的运算过程和有效性。

工期窗口指派可控处理时间资源约束最大费用最小化排序问题

【目的】研究具有公共工期窗口指派的凸资源单机排序问题。【方法】任务的处理时间与所在位置有关,并且可以通过分配一定的资源加以控制,是所获得的资源量的凸函数。目标函数是所有任务费用中的最大值。考虑两个问题。第1个问题是在资源总量有上界限制条件下,确定任务的最优排序、公共工期窗口位置和大小以及资源分配方案,使得最大费用最小。第2个问题是在最大费用有上界限制条件下,求出最小资源总量、任务排序和公共工期窗口位置和大小,使得资源总量最小。【结果】将上述问题转化为非线性凸规划问题和指派问题加以处理。证明了两个问题均可以在多项式时间内求解。【结论】对于考虑的两个问题分别给出了多项式时间最优算法。

一类随机绝对超前-延误惩罚单机排序

研究在一台随机发生故障的机器上加工n个具有同一工期的工件,使得所谓绝对超前-延误惩罚的数学期望最小的调度问题.详细地讲,问题中的目标测度是最小化完工时间与公共工期之绝对偏差和的数学期望.我们在机器的工作时间服从指数分布的条件下分中断-恢复型问题和中断-重复型问题进行研究(对于中断-重复型要求故障时间服从指数分布或是一个常数).主要工作如下:(1)问题规划和预备知识.建立支持后续工作的定义,关系和事实.特别地,证明了一个加工时间为t的工件的完工时间与任一工期之绝对偏差的数学期望是关于变量t的半V型函数;(2)最优解的性质.给出了最优解的几个特征.最重要的是,证明了最优解具有半V型性质;(3)算法.讨论了几个关于求所研究问题最优解的计算问题.