1.3.1 车间调度问题的描述及分类
车间调度问题可以描述为：n个工件在m台机器上加工。一个工件有多道工序，每道工序可以在若干台机器上加工，并且必须按可行的工艺次序进行加工；每台机器可以加工工件的若干工序，并且在不同的机器上加工的工序集可以不同。车间调度的目标是将工件合理地安排到各台机器上，并合理地安排工件的加工次序和开始时间，以使约束条件被满足，同时优化一些性能指标。在实际制造系统中，还要考虑刀具、托盘和物料搬运系统的调度问题。
车间调度问题的分类方法较多，根据工件和车间构成不同可分为：
（1）单机调度问题（Single Machine Scheduling Problem，SMP）
加工系统只有一台机床，待加工的工件有且仅有一道工序，所有工件都在该机床上进行加工。此问题是最简单的调度问题，生产车间出现瓶颈机床时的调度就可视为此类调度问题。
（2）并行机调度问题（Parallel Machine Scheduling Problem，PMP）
加工系统中有多台完全相同的机床，每个工件只有一道工序，工件可以在任意一台机床上进行加工。
（3）开放车间调度问题（Open Shop Scheduling Problem，OSP）
每个工件各工序的加工顺序是任意的。工件的加工可以从任何一道工序开始，在任何一道工序结束。工件的加工没有特定的技术路线约束，各工序没有先后关系约束。
（4）流水车间调度问题（Flow Shop Scheduling Problem，FSP）
加工系统有一组功能不同的机床，待加工的工件包含多道工序，每道工序在一台机床上加工，所有工件的加工路线都是相同的。每个工件的工序有先后顺序约束。
（5）作业车间调度问题（Job Shop Scheduling Problem，JSP）
加工系统有一组功能不同的机床，待加工的工件包含多道工序，每道工序在一台机床上加工，工件的加工路线互不相同。每个工件的工序有先后顺序约束。
一般调度问题采用“n/m/A/B”来表示。其中，n表示工件数目；m表示机器数目；A表示工件流经机器形态的类型；B表示性能指标。
B的形式多种多样，大体可分成以下几类：
①基于加工完成时间的性能指标，如Cmax（最大完工时间）、Fmax（最大流经时间）等；
②基于交货期的性能指标，如Lmax（最大推迟完成时间）、Tmax（最大拖后时间）等；
③多目标综合性能指标，如最大完工时间与最大推迟完成时间的综合等。
车间调度具有以下特点：
（1）多约束性
通常情况下，工件的加工路线是已知的，并且受到严格的工艺约束，因此各道工序在加工顺序上具有先后约束关系。同时，工件的加工机器集是已知的，工件必须按照工序在可以选择的机床上进行加工。
（2）离散性
车间生产系统是典型的离散系统，属于离散优化问题。工件的开始加工时间、任务的到达、订单的变更及设备的增添或故障等都是离散事件。可以利用数学规划、离散系统建模与仿真、排序理论等方法对车间调度问题进行研究。
（3）计算复杂性
车间调度是一个在若干等式和不等式约束下的组合优化问题，从计算时间复杂度看是一个NP-hard问题。随着调度规模的增大，问题可行解的数量呈指数级增加。例如，工件和机器的数量均为10的单机车间调度问题，当单纯考虑加工周期最短时，可能的组合数就已达到10！。
（4）不确定
实际车间调度中有很多随机不确定的因素，如工件到达时间的不确定，工件的加工时间随不同的加工机器也有一定的不确定。另外，系统中常有突发事件，如紧急订单插入、订单取消、原材料紧缺、交货期变更、设备发生故障等。
（5）多目标性
在不同类型的生产企业和不同的生产环境中，调度目标往往形式多样、种类繁多，如完工时间最短、交货期最早、设备利用率最高、成本最低、在制品库存量最小等。多目标性的含义有两个，一个是目标的多样性，另一个是多个目标需要同时得到满足，并且各个目标往往是相互冲突的。
车间调度问题的特点使得车间调度问题从产生至今一直吸引着来自不同领域的研究人员寻求有效方法对其求解，但是，多年来仍不能完全满足实际应用的需要，促使人们更加深入、全面地对其进行研究，以提出更有效的理论和方法来满足企业的实际需求。