zh %E5%BC%80%E6%94%BE%E8%BD%A6%E9%97%B4%E8%B0%83%E5%BA%A6

开放车间调度（英語：Open-shop scheduling）也被称为开放车间调度问题（英語：open-shop scheduling problem，OSSP），是计算机科学以及运筹学领域中的最佳化问题。这是最优作业调度的一种变体，在一般的最优作业调度问题中，首先给定 $J_{1},J_{2},...,J_{n}$ 共 $n$ 个作业，每项作业都具有不同的处理时间。我们需要做的就是将这n项作业安排到m台处理能力不同的机器上，并要求最小化加工周期。而在开放车间调度这一变体中，每项作业都存在一组操作 $O_{1},...,O_{n}$ ，所有的操作都需要处理，但可以按照任意的顺序进行。这一类型的问题最初是在1976年由特奥菲洛·F·冈萨雷斯与萨塔吉·萨尼进行研究的。^[1]

在最优作业调度问题的标准三字段表示法中，开放车间变量在第一个字段用O表示。例如，O3| $p_{ij}$ | $C_{\max }$ 就可以表示为一个具有单元处理时间的3台机器作业车间问题，其目标是最小化最大完工时间。

定义

在开放车间调度问题中，我们需要输入一组工作和一组工作站，以及一张二维的表格，该表格记录了每项作业在每个工作站所花费时间。每项作业在同一时间只能在一个工作站上处理，同时每个工作站一次只能处理一项作业。然而与作业车间调度问题不同的是，这类问题每步操作的顺序都可以自由变化。目标是为每个工作站要处理的每项作业分配一个时间，避免多项作业在同一时间分配到同一工作站以及一项作业在同一时间分配到多个工作站，并且每项作业在期望的时间内完成任务。通常衡量解决方案好坏的标准是它的加工周期，即从进度表的开始（第一个任务分配到第一个工作站）到结束（最后一个工作站完成最后一项任务）的时间量。

计算复杂度

如果只有两项作业或两个工作站，那么开放车间调度问题可以在多项式时间内求解。如果说所有不等于0的解决时间都相等，那么这种问题也可以在多项式时间内完成。因为在这种情况下，这个问题可以等效于给一个以作业和工作站为顶点的二分图的边上色，每条边代表不为0的作业-工作站对，着色中边的颜色对应于工作-工作站对被安排处理的时间段。由于二分图的线图是完美图，所以二分图可以在多项式时间内实现边着色。

对于三个以上任务以及工作站并且处理时间不相同的问题，难度为NP困难。^[2]

参考文献

^ Gonzalez, Teofilo; Sahni, Sartaj, Open shop scheduling to minimize finish time, Journal of the ACM, 1976, 23 (4): 665–679, CiteSeerX 10.1.1.394.1507 , MR 0429089, doi:10.1145/321978.321985 .
^ Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.; Lenstra, J. K.; Sevast'janov, S. V.; Shmoys, D. B., Short shop schedules, Operations Research, 1997, 45 (2): 288–294, JSTOR 171745, MR 1644998, doi:10.1287/opre.45.2.288

[1] Gonzalez, Teofilo; Sahni, Sartaj, Open shop scheduling to minimize finish time, Journal of the ACM, 1976, 23 (4): 665–679, CiteSeerX 10.1.1.394.1507 , MR 0429089, doi:10.1145/321978.321985 .

[2] Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.; Lenstra, J. K.; Sevast'janov, S. V.; Shmoys, D. B., Short shop schedules, Operations Research, 1997, 45 (2): 288–294, JSTOR 171745, MR 1644998, doi:10.1287/opre.45.2.288

[1]

[2]