货物尺寸相同的2维装箱问题的等价类(英文)

在生产与储运领域,把小长方体货物（盒子）装入大长方体箱子是一项重要的工作.本文涉及的问题是:把相同尺寸（a×b×c）的盒子装到一个箱子X×Y×Z中,使所装入箱子的盒子数量为最大.由于某些条件的限止,有时要求货物只能按一个重力方向进行装箱,从而使装箱问题变为把尺寸相同的2维盒子（a×b）填装到一个2维箱子X×Y中.本文讨论当盒子尺寸（a×b包括 b×a）给定,箱子尺寸充分大时,在本文所给的等价意义下,共有多少种互不等价的箱子X×Y.

与装箱(切割)问题有关的数论结果

在生产与储运领域,把(小的)矩形货物装入(大的)矩形箱子是一项重要的工作。本文回答了以下的问题:设有一个长度为X的一维箱子以及设有两种(或三种)长度分别为a,b(或a,b,c)的货物许多,问在什么条件下,可以(或不能)用这些货物(假定货物数量不限)装满箱子?或当两(或三)种货物的长度a,b(或a,b,c)给定时,一维箱子的长度X为多大时,用这两(或三)种货物能或不能装满箱子?不能被这些货物装满的箱子有多少个?

加工时间为线性增函数有上界的排序问题

本文讨论工件的加工时间是其开工时间的一类线性增加函数有上界的单机排序问题1|pj(t)(t0,T1,T2)|Cmax:设工件集J=J1,J2,…,Jn中的每个工件需要在一台机器上得到加工;工件集J被划分成两组J=Ω1+Ω2;机器上第一个被加工的工件在时刻t0>0开始加工;Ω1中工件的加工时间为pj(t)=ajt(当t<T1)或pj(t)=ajT1(当t≥T1),Ω2中工件的加工时间为pj(t)=ajt(当t<T2)或pj(t)=ajT2(当t≥T2),其中T2>T1>t0均是给定的常数,t表示对应工件的开工时刻;排序的目的是极小化时间表长(最大完工时间)Cm ax。在所得的引理2和引理3的基础上,本文给出一个复杂度为nlogn的多项式时间算法,从而也证明了所讨论的问题是多项式时间可解得的。

最优解唯一的线性规划问题

给出了线性规划问题最优解何时唯一存在的充分必要条件,从而一方面彻底解决了线性规划何时最优解唯一存在的问题,另一方面也纠正和弥补了一些教材或专著在此问题上的错误和不足.

偏序集最小顶点割算法与最小费用赶工问题

在网络计划问题中,一项大的工程由许多工序合成。工序与工序之间存在着一定的前后关系,每个工序有着自己的正常加工时间和通过赶工所能达到的最短加工时间以及每赶工一天的赶工费用。设一项工程的正常工期为T天,通过对所有可能的工序赶工,整个工程能达到的最短工期为S天。本文的问题是,对于任意给定的t(S t<T),怎样确定所要赶工的工序及其赶工天数,在满足整个工程的完工时间恰为t天的条件下,使总的赶工费用最小。本文对这一问题给出了一个方便易行的有效算法,并将以往在(双代号)网络图上对工程工期的计算改为在工程的偏序图上进行,从而省去了烦琐的工程网络图(即偏序集的箭线图)的绘制。

依赖机器的两台机自由作业排序问题

研究加工时间仅依赖于机器的两台机自由作业排序问题O_2|p_(ij)=p_i,p_2<p_1<2p_2,Non-Idle|ΣC_j.项思明和唐国春(1998)证明了可将该问题转化成指派问题.俞文(?)和应刚(1998)给出了这一问题的显式解,并用较长的篇幅证明其显式解的正确性;他们还举例说明所给出的显式最优排序并不排除其他形式的最优解的存在;但他们未说明所给出的显式解何时才是唯一最优解.将给出问题O_2|p_(ij)=p_i,p_2<p_1<2p_2,Non-Idle|∑C_j的显式解的直观的最优性证明,并讨论问题显式解何时是唯一的最优解.

一个关于非对称距离的旅行商问题的迭代算法

本文对非对称距离的旅行商问题,给出了一个迭代算法,并分析了此迭代算法的复杂度为M O(N4),其中,N是问题中旅行商所要经过的城镇数,M是两城镇间的最大距离。最后用实例对此算法进行了验算和说明。

关于最优解唯一的线性规划问题的讨论

本文讨论了线性规划问题最先解唯一的几种情形及其判定.从而弥补和纠正了一般教材在这方面的不足。

一个绘制统筹图的算法

统筹图又叫计划网络图。任给一个其元素叫做工序（或作业或活动）的有限偏序集，要绘制它的一个最优统筹图，限含虚工序数目为最少者，是一个尚未从理论上解决的问题。本文讨论了虚工序产生的原因和如何减少虚工序数量的一些途径；指出了高度为二的偏序集其最优统筹图含虚工序数目达到最大且等于该偏序集框图的边数的充分必要条件；本文给出了一个绘制最优统筹图的近似算法，此算法弥补了文［２］和［３］所给算法的一些不足之处。

关于序集维度问题的可去点对

设P是一有限序集,a、b∈P,称{a,b}是可去的是指,dim(P-{a,b})≥dimP-1。本文指出,如果有限序集P不含子序集N,则P的每个临界对都是可去的。

碰撞数问题Greedy序集的结构

称一有限序集是一Greedy序集是指,它的每个关于碰撞数问题的Greedy线性扩张都是最优的。本文给出了Greedy序集的结构。

人员紧急运输问题

设在A地集结有人员若干,以及少量的用于运送人员的车辆(或其他运输工具,以下统称汽车).现需要将这些人员全部通过现有的汽车运送,以及徒步行走的方式尽快到地赶到B地.问:如何安排汽车的行程以及人员的行走.

加工时间线性恶化的成组加工流水作业问题

文章讨论了m台机器的Flow Shop成组加工问题,工件在不同机器上的加工时间以相同的系数(斜率)线性恶化,目标函数分别为极小化时间表长和总完工时间.对于目标函数为极小化时间表长的Flow Shop成组加工问题,再进一步细分为组间无调整时间和组间有相同调整时间的两种情形来讨论,都得到了最优调度(排序).对于目标函数为总完工时间的Flow Shop成组加工问题,只要组内按q(?)单调递增(SPT)序加工,组间按S_i单调递增序加工可得最优调度.

机器使用时间受限的线性恶化成组排序问题

讨论了单机成组加工问题,工件加工时间是开工时间的简单线性恶化函数,并假设机器在某一时间段内不能进行工件的加工,目标函数为极小化时间表长。给出了该问题的一种0-1整数规划解法。

加工时间依赖资源的流水作业资源分配问题

本文研究加工时间受资源影响的流水作业时间表长问题。对问题F2|chain,∑nj=1μj ^U|Cmax给出了问题求最优解的多项式时间算法。

带到达时间的单机排序中的资源分配问题

讨论两个单机排序的资源分配问题1|rj,pj=bj-ajuj,Cmax≤^C|∑uj和1|rj,prec,pj=bj-ajujCmax≤^C|∑uj并给出求其最优资源分配的多项式算法。

同时具有学习和恶化效应的单机成组排序问题

讨论了一类工件的加工时间具有学习效应且安装时间带有恶化的成组排序问题,目标函数分别为极小化最大完工时间和极小化总完工时间,1|pij=aij-bijt,S=δit,GT|Cmax,1|pij=aij-bijt,S=δit,GT|∑Cij,并分别给出了求最优解的多项式时间算法,其中极小化总完工时间问题是在bij=b,δi=δ的特殊情况下给出的。

遗传算法求解一类排序问题

考虑一类分段恶化单机问题,得到了最优解的性质,根据这些性质设计了一种求近似最优解的遗传算法。通过分支定界法对小规模算例的验证表明,本遗传算法获得精确解的比例是高的,由此认为所给遗传算法是很有效的。

最优箭线图的判定与唯一性

统筹图又叫计划网络图或箭线（工程）图．任给一个有限偏序集（简称序集，其元素叫做工序或作业），要绘制它的一个最优统筹图（含虚工序数最少者）是一个尚未解决的困难问题．本文给出了一个判定一序集存在唯一最优箭线图的充分条件以及绘制这类序集的最优箭线图的方法；并指出：若Ｐ一个序集满足Ｗ－ｆｒｅｅ和Ｍ－ｆｒｅｅ，则Ｐ的最优箭线图唯一且可在多项式时间内作出．

一种可控的两台机流水作业排序问题

在经典的两台机流水作业排序问题F_2‖C_(max)的基础上进行修改,将工件J_j在两台机上的加工时间由常数A_j和B_j改成A_j(x)=a_j+c_jx和B_j(x)=b_j-d_jx,其中x是某区间上的可控(决策)变量.排序的目标是,选择适当的x(对应相应的加工时间是A_j(x)、B_j(x))(j=1,2,…,n)及相应的工件的加工顺序σ=[σ(1),σ(2),…,σ(n)],使时间表长(即最后一个工件J_σ(n)在第二台机上的完工时间)G_(max达到最小.给出了解决问题的有效方法.