自由作业(Openshop)排序问题可以简单的做如下描述：假定有n个独立工件和m台不同的机器，工件必须经过所有的机器加工处理，而且工件经过机器的顺序以及机器加32T件的顺序都没有特定的要求。自由作业排序问题在实际生活中的例子包括医院的健康检查和汽车去修车厂保养等。 生产过程中的排序往往受到产品生产的特性或者生产技术的限制，所以会产生不同的约束情况，例如：无等待时间(Nowait)是化学、石油工业和冶金工业的特色；阻塞(Blocking)指的是缓存(Buffer)能力受到限制或者没有缓存的情况，最常见的是利用机器人进行夹取工件的作业。对于双机自由作业排序问题而言，Nowait和Blocking约束具有等价性。 本文针对具有无等待时间限制的双机自由作业排序问题，以最大流程时间(Makespan)最小化为研究目标，设计了一个启发式算法，利用启发式算法我们可以迅速而有效的解决大规模排序问题；我们还通过计算实验证明该算法与已有的算法相比具有更好的性能。为了寻求小规模问题的最优解，我们进一步设计了基于分支定界算法的最优算法，并将启发式算法的计算结果作为分支定界算法的上界。同时，我们还设计了分支定界的分支策略和下界的计算方法，并针对不同规模的问题评估了算法的计算时间。