算法笔记——回溯法作业调度问题和符号三角形问题

1、批作业调度问题

(1)问题描述

设有n个作业组成的系统{J₁,J₂,…,Jₙ}。每一个作业必须首先在第一台机器上进行加工（即依次在第一台和第二台机器上加工）。每个作业所需时间为t_ji。对于任意一个确定的生产调度π，在第j台设备上的完工时间为F_{j,i}。所有产品经过第j台设备后的总完工时间之和定义为该生产调度的总运行时间。

针对批处理作业调度问题而言，在给定的n个作业中确定最优作业安排策略以使总完成时间最小化

__ 例：设n=3，考虑以下实例：

对于这三项作业的所有六个可能调度顺序（即排列组合），分别计算了它们各自的完成时间：（按照排列顺序）[（排列）]其结果依次为：t_{{\rm 完成}} = 19, t_{{\rm 完成}} = 18, t_{{\rm 完成}} = 20, t_{{\rm 完成}} = 21, t_{{\rm 完成}} = 19, 和 t_{{\rm 完成}} = 19。显然地，在这些排列组合中能够达到最小总完成时间的最佳调度顺序为（具体排列式），其总完成时间为t_{{\rm 最优}}} = 18。

**