论文部分内容阅读
摘 要：针对具有序列相关的带准备时间的单机调度问题，其优化目标为实现最大完工时间的最小化。考虑到问题的NP难特性以及大规模求解的需要，首先建立了数学模型。然后结合禁忌搜索算法的基本原理和算法步骤，设计了一个求解上述问题的禁忌搜索算法。并通过多组实验测试为不同规模的算例选择了合适的禁忌长度。实验结果表明禁忌搜索算法能够有效地解决这类调度问题，并且在大规模问题上明显优于商业软件。
关键词：准备时间 单机调度 禁忌搜索算法 禁忌长度
一、引言
在生产调度研究领域，单机环境研究是复杂车间调度问题建模和算法设计的基础。本文研究了一类具有序列相关的（Sequence dependent）带准备时间的单机调度问题，该问题可描述如下：n项不同的作业在一台机器上加工，每项作业都有预期完成时间以及加工时间，当机器从加工一项作业切换到加工另一项作业时，需要相应的准备时间。该类准备时间依赖于前后两项作业的排班顺序，调度目标即要找到一个最优的工作序列实现最大完工时间的最小化。该类问题已经被证明为NP难的。
目前，国内外文献中已有大量关于单机调度问题的研究。在精确算法方面，Monma和Potts最先提出了一种通用的动态规划算法，Ghosh和Gupta在此基础上，提出了一种新的动态规划方法，一定程度上降低了算法的复杂度。Hariri和Potts设计了一种分支定界方法，可求解的问题规模最大达到50个作业。考虑到算法复杂度的限制，上述精确算法均无法解决大规模的实际问题，因此，启发式算法开始受到广泛关注。Gagnie和Price等比较了蚁群算法和其它启发式算法，结果表明蚁群算法在处理大规模的单机调度问题时有明显的优势。文献针对该类问题提出了两种启发式算法：局部搜索算法和贪婪随机自适应搜索算法。文献设计了一种通用变邻域搜索算法（GVNS），其计算性能远远优于此前提出的各类算法。国内相关文献提出混合邻域搜索算法[8]和遗传算法等方法来求解相关单机调度问题。本文通过对带准备时间的单机调度问题的研究，提出了一种禁忌搜索算法，在一定程度上丰富了该类问题的求解。
二、带准备时间的单机调度问题。
1. 问题描述。假设n为待处理的作业总数，J为所有作业的集合，记为J={1，2，3，…n}；每个作业i都有加工时间（processing time），记为Pi；预期完成时间（due date）记为di；作业的准备时间（setup time）依赖于整个工作序列的排列顺序（sequence-dependent），即假如作业i在工作序列中排在第k位，作业j排在第k+1位，那么作业j排在作业i后的准备时间则为sij。作业i如果作为工作序列的第一个工作，则有一个初始准备时间s0i。用排列π={π1，π2，π3，…πn}表示一个调度方案，πi表示整个工作序列中第i个加工的作业，其完成时间记为Ci=Ci-1+s（πi-1）πi+Pπi。那么整个工作序列中，最大完工时间则记为Cn=Cn-1+s（πn-1）πn+Pπn。本文所研究的带准备时间的单机调度问题中，对于任意的i，s0i均为0，这一简化并不会影响问题本身的难度。而优化目标就是最小化最大完工时间Cn。
2. 初始模型建立。
2.1模型建立。
2.2模型说明。
分析上述模型，我们不难看出其目标函数中含有两个0-1变量相乘的二次项，表示只有两个变量均为1时，sij才计在总的准备时间里，反之亦然。
三、算法设计
1.禁忌搜索算法的基本框架
1.1编码方法：作业工序的全排列，如作业集合为N={1，2，3，4，5}，则本文将解表示为一个长度为5的顺序表，例如{3，1，2，5，4}即为其中一个解。
1.2邻域结构：采用互换法进行邻域操作，即随机对换两个作业工序的2-opt，这种互换法每个状态的邻域解有个。
1.3禁忌长度：因问题规模不同而变化，通过多次实验进行确定。
1.4评价函数：以排班中的最大完工时间为评价函数，评价值越小越好。
1.5候选集合：从邻域中选择若干个评价值最佳的邻居组成候选集合，集合大小与问题规模有关。
1.6初始解：以产生随机数的形式生成一个工序的全安排，作为初始解。
1.7特赦准则：当候选集合中的邻居对应的评价值均比当前最佳评价值差时，而禁忌表中的某一2-opt对应的评价值要优于当前最佳评价值，则解禁该2-opt。
1.8终止规则：确定迭代时间终止。
2. 算例设计。
1.1作业规模：分别选取10种作业规模：15，30，45，60，75，90，105，120，135，150。
1.2禁忌长度：针对上述作业规模，确定最小禁忌长度集合：2，4，6，8，10，12，14，16，18，20；最大禁忌长度集合：20，40，60，80，100，120，140，160，180，200；禁忌長度变化步长：2，4，6，8，10，12，14，16，18，20。通过多次实验来观察禁忌长度对最终结果的影响。
1.3候选集合：候选解在当前解的邻域中产生，不同问题规模对应的候选集合大小为：100，300，600，1000，1500，2000，2500，3000，4000，6000。
1.4迭代时间：10，50，100，150，200，250，300，350，400，450（单位为s）。
四、实验结果
本文用C语言实现了上述单机调度问题的禁忌搜索算法，并对随机生成的10个不同规模的算例在i3-2370M CPU @2.40GHz、内存为2.00GB的计算机上进行了测试。
1.对禁忌长度的讨论。对每一种规模的算例通过控制其他参数，分别选取了10个不同的禁忌长度来进行实验分析，以此选定合适的取值。分析可得：多数算例在禁忌长度取值近似为1.5为候选集合中候选解的个数）时计算结果比较理想。 2.结果比较。在研究了禁忌长度的取值规律之后，为了验证算法的有效性，我们将其运行结果与商业软件cplex的求解结果进行比较，结果如表1所示：
由表1我们可以得知：在运行时间相同的前提下，商业软件在较小规模的问题求解中计算效率明显优于禁忌搜索算法，甚至可以很快得到最优解。但是在规模为45甚至更大的算例中，禁忌搜索算法的优势则大大体现，计算效果均明显好于商业软件。特别是在规模135和150的问题中商业软件甚至没有在设定时间内得到一个可行解，而禁忌搜索算法则可以最终得到一个较好的上界。
五、结语
本文基于生产车间作业的实际背景，分析了带准备时间的单机调度问题的研究现状和数学模型。在对禁忌搜索算法基本原理进行研究的基础上，针对问题特点，设计了一个禁忌搜索算法，并对禁忌长度的选择进行了多次实验测试。实验结果表明，该算法能够找到较高质量的上界，并且解的质量受到作业规模、计算时间、禁忌长度等因素的影响。这在实际生产决策中有着很强的经济意义，可以帮助决策者在短时间内做出一个切实可行的排班计划。
参考文献：
[1] 钟涛，萧卫，徐宏云. 带准备时间的单机调度问题的混合进化算法研究[J]. 计算机应用研究，2013（11）：3248-3252.
[2] Monma CL，Potts CN. On the complexity of scheduling with batch setup times[J]. Operations Research，1989， 37：798-804.
[3] Ghosh JB， Gupta JND. Batch scheduling to minimize maximum lateness[J]. Operations Research Letters，1997， 21：77-80.
[4] Hariri AMA， Potts CN. Single machine scheduling with batch setup times to minimize maximum lateness[J]. Annals of Operations Research， 1997， 70：75-92.
[5] GAGNIE C，PRICE W L，GRAVEL M.Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence—dependent setup times[J].Journal of the Operational Research Society，2002，53（8）：895-906.
[6] GUPTA S R，SMITH J S.Algorithms for single machine total tardiness scheduling with sequence dependent setups[J].European Journal of Operational Research，2006，175（2）：722-739.
[7] KIRLIK G，OGUZ C.A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine[J].Computers & Operations Research，2012，39（7）：1506-1520.
[8] 曾立平.求解工件加工調度问题的一种混合邻域搜索算法[D].武汉：华中科技大学，2006.
[9] 侯福均，吴祈宗.应用遗传算法求解模糊参数的单机调度问题[J].北京理工大学学报，2006，26（3）：260—263.
作者简介：李春燕（1991.01—），女，同济大学经济与管理学院硕士研究生。研究方向：现代物流与供应链管理。
关键词：准备时间 单机调度 禁忌搜索算法 禁忌长度
一、引言
在生产调度研究领域，单机环境研究是复杂车间调度问题建模和算法设计的基础。本文研究了一类具有序列相关的（Sequence dependent）带准备时间的单机调度问题，该问题可描述如下：n项不同的作业在一台机器上加工，每项作业都有预期完成时间以及加工时间，当机器从加工一项作业切换到加工另一项作业时，需要相应的准备时间。该类准备时间依赖于前后两项作业的排班顺序，调度目标即要找到一个最优的工作序列实现最大完工时间的最小化。该类问题已经被证明为NP难的。
目前，国内外文献中已有大量关于单机调度问题的研究。在精确算法方面，Monma和Potts最先提出了一种通用的动态规划算法，Ghosh和Gupta在此基础上，提出了一种新的动态规划方法，一定程度上降低了算法的复杂度。Hariri和Potts设计了一种分支定界方法，可求解的问题规模最大达到50个作业。考虑到算法复杂度的限制，上述精确算法均无法解决大规模的实际问题，因此，启发式算法开始受到广泛关注。Gagnie和Price等比较了蚁群算法和其它启发式算法，结果表明蚁群算法在处理大规模的单机调度问题时有明显的优势。文献针对该类问题提出了两种启发式算法：局部搜索算法和贪婪随机自适应搜索算法。文献设计了一种通用变邻域搜索算法（GVNS），其计算性能远远优于此前提出的各类算法。国内相关文献提出混合邻域搜索算法[8]和遗传算法等方法来求解相关单机调度问题。本文通过对带准备时间的单机调度问题的研究，提出了一种禁忌搜索算法，在一定程度上丰富了该类问题的求解。
二、带准备时间的单机调度问题。
1. 问题描述。假设n为待处理的作业总数，J为所有作业的集合，记为J={1，2，3，…n}；每个作业i都有加工时间（processing time），记为Pi；预期完成时间（due date）记为di；作业的准备时间（setup time）依赖于整个工作序列的排列顺序（sequence-dependent），即假如作业i在工作序列中排在第k位，作业j排在第k+1位，那么作业j排在作业i后的准备时间则为sij。作业i如果作为工作序列的第一个工作，则有一个初始准备时间s0i。用排列π={π1，π2，π3，…πn}表示一个调度方案，πi表示整个工作序列中第i个加工的作业，其完成时间记为Ci=Ci-1+s（πi-1）πi+Pπi。那么整个工作序列中，最大完工时间则记为Cn=Cn-1+s（πn-1）πn+Pπn。本文所研究的带准备时间的单机调度问题中，对于任意的i，s0i均为0，这一简化并不会影响问题本身的难度。而优化目标就是最小化最大完工时间Cn。
2. 初始模型建立。
2.1模型建立。
2.2模型说明。
分析上述模型，我们不难看出其目标函数中含有两个0-1变量相乘的二次项，表示只有两个变量均为1时，sij才计在总的准备时间里，反之亦然。
三、算法设计
1.禁忌搜索算法的基本框架
1.1编码方法：作业工序的全排列，如作业集合为N={1，2，3，4，5}，则本文将解表示为一个长度为5的顺序表，例如{3，1，2，5，4}即为其中一个解。
1.2邻域结构：采用互换法进行邻域操作，即随机对换两个作业工序的2-opt，这种互换法每个状态的邻域解有个。
1.3禁忌长度：因问题规模不同而变化，通过多次实验进行确定。
1.4评价函数：以排班中的最大完工时间为评价函数，评价值越小越好。
1.5候选集合：从邻域中选择若干个评价值最佳的邻居组成候选集合，集合大小与问题规模有关。
1.6初始解：以产生随机数的形式生成一个工序的全安排，作为初始解。
1.7特赦准则：当候选集合中的邻居对应的评价值均比当前最佳评价值差时，而禁忌表中的某一2-opt对应的评价值要优于当前最佳评价值，则解禁该2-opt。
1.8终止规则：确定迭代时间终止。
2. 算例设计。
1.1作业规模：分别选取10种作业规模：15，30，45，60，75，90，105，120，135，150。
1.2禁忌长度：针对上述作业规模，确定最小禁忌长度集合：2，4，6，8，10，12，14，16，18，20；最大禁忌长度集合：20，40，60，80，100，120，140，160，180，200；禁忌長度变化步长：2，4，6，8，10，12，14，16，18，20。通过多次实验来观察禁忌长度对最终结果的影响。
1.3候选集合：候选解在当前解的邻域中产生，不同问题规模对应的候选集合大小为：100，300，600，1000，1500，2000，2500，3000，4000，6000。
1.4迭代时间：10，50，100，150，200，250，300，350，400，450（单位为s）。
四、实验结果
本文用C语言实现了上述单机调度问题的禁忌搜索算法，并对随机生成的10个不同规模的算例在i3-2370M CPU @2.40GHz、内存为2.00GB的计算机上进行了测试。
1.对禁忌长度的讨论。对每一种规模的算例通过控制其他参数，分别选取了10个不同的禁忌长度来进行实验分析，以此选定合适的取值。分析可得：多数算例在禁忌长度取值近似为1.5为候选集合中候选解的个数）时计算结果比较理想。 2.结果比较。在研究了禁忌长度的取值规律之后，为了验证算法的有效性，我们将其运行结果与商业软件cplex的求解结果进行比较，结果如表1所示：
由表1我们可以得知：在运行时间相同的前提下，商业软件在较小规模的问题求解中计算效率明显优于禁忌搜索算法，甚至可以很快得到最优解。但是在规模为45甚至更大的算例中，禁忌搜索算法的优势则大大体现，计算效果均明显好于商业软件。特别是在规模135和150的问题中商业软件甚至没有在设定时间内得到一个可行解，而禁忌搜索算法则可以最终得到一个较好的上界。
五、结语
本文基于生产车间作业的实际背景，分析了带准备时间的单机调度问题的研究现状和数学模型。在对禁忌搜索算法基本原理进行研究的基础上，针对问题特点，设计了一个禁忌搜索算法，并对禁忌长度的选择进行了多次实验测试。实验结果表明，该算法能够找到较高质量的上界，并且解的质量受到作业规模、计算时间、禁忌长度等因素的影响。这在实际生产决策中有着很强的经济意义，可以帮助决策者在短时间内做出一个切实可行的排班计划。
参考文献：
[1] 钟涛，萧卫，徐宏云. 带准备时间的单机调度问题的混合进化算法研究[J]. 计算机应用研究，2013（11）：3248-3252.
[2] Monma CL，Potts CN. On the complexity of scheduling with batch setup times[J]. Operations Research，1989， 37：798-804.
[3] Ghosh JB， Gupta JND. Batch scheduling to minimize maximum lateness[J]. Operations Research Letters，1997， 21：77-80.
[4] Hariri AMA， Potts CN. Single machine scheduling with batch setup times to minimize maximum lateness[J]. Annals of Operations Research， 1997， 70：75-92.
[5] GAGNIE C，PRICE W L，GRAVEL M.Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence—dependent setup times[J].Journal of the Operational Research Society，2002，53（8）：895-906.
[6] GUPTA S R，SMITH J S.Algorithms for single machine total tardiness scheduling with sequence dependent setups[J].European Journal of Operational Research，2006，175（2）：722-739.
[7] KIRLIK G，OGUZ C.A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine[J].Computers & Operations Research，2012，39（7）：1506-1520.
[8] 曾立平.求解工件加工調度问题的一种混合邻域搜索算法[D].武汉：华中科技大学，2006.
[9] 侯福均，吴祈宗.应用遗传算法求解模糊参数的单机调度问题[J].北京理工大学学报，2006，26（3）：260—263.
作者简介：李春燕（1991.01—），女，同济大学经济与管理学院硕士研究生。研究方向：现代物流与供应链管理。