Evolutionary algorithm for stochastic job shop scheduling with random processing time
Evolutionary algorithm for stochastic job shop scheduling with random processing time
复制标题
DOI：
10.1016/j.eswa.2011.09.050
复制
发表时间：
2012-02
期刊：
影响因子：
--
通讯作者：
S. Horng;Shieh-Shing Lin;Feng-Yi Yang
中科院分区：
文献类型：
--
作者：
S. Horng;Shieh-Shing Lin;Feng-Yi Yang
针对随机作业车间调度问题（SJSSP），提出了一种嵌入进化策略（ES）的有序优化（OO）进化算法，简称ESOO，以在有限的计算时间内最小化存储费用和延迟惩罚的期望总和为目标，求解足够好的调度问题。首先，使用模拟长度较短的随机模拟的粗糙模型作为ES中的适应度逼近，从搜索空间中选择N个大致良好的调度。接下来，从选定的N个大致较好的时间表开始，进行目标软化过程，以寻找一个足够好的时间表。最后，将提出的ESOO算法应用于由8台机器上的8个作业组成的SJSSP，该SJSSP具有截断正态分布、均匀分布和指数分布的随机处理时间。通过与五种典型调度规则的仿真测试结果进行比较，结果表明该方法在求解质量和计算效率方面获得了足够好的调度规则。
In this paper, an evolutionary algorithm of embedding evolutionary strategy (ES) in ordinal optimization (OO), abbreviated as ESOO, is proposed to solve for a good enough schedule of stochastic job shop scheduling problem (SJSSP) with the objective of minimizing the expected sum of storage expenses and tardiness penalties using limited computation time. First, a rough model using stochastic simulation with short simulation length will be used as a fitness approximation in ES to select N roughly good schedules from search space. Next, starting from the selected N roughly good schedules we proceed with goal softening procedure to search for a good enough schedule. Finally, the proposed ESOO algorithm is applied to a SJSSP comprising 8 jobs on 8 machines with random processing time in truncated normal, uniform, and exponential distributions. The simulation test results obtained by the proposed approach were compared with five typical dispatching rules, and the results demonstrated that the obtaining good enough schedule is successful in the aspects of solution quality and computational efficiency.