Two-stage Optimal Modeling and Algorithm of Production Scheduling for Steelmaking and Continuous Casting
-
摘要: 以某钢厂多台转炉及多台精炼炉对多台连铸机的复杂生产线为研究对象，针对其调度过程涉及多设备、多目标、多约束等调度要素，且离散和连续变量混杂，采用常规建模方法难以满足现场对调度的精度及排产速度的需求问题，提出一种新型的两阶段优化建模方法.首先，证明了炉次从炼钢到连铸总等待时间最小的调度目标与该炉次在转炉开始作业时间最大是等价的事实，并以离散型的设备变量为决策变量，以转炉开始作业时间最大为动态规划最优指标，建立设备指派多阶段动态规划基本方程和设备指派优化模型；然后，以炉次在设备开始作业时间的连续型变量为决策变量，并将准时开浇的非线性调度指标转化成与之等价的线性优化目标，以在同一台连铸机上浇铸的炉次之间断浇的时间间隔最小、钢包在设备之间的冗余等待时间最小、提前与滞后理想开浇时间的时间间隔最小为目标，建立线性规划冲突解消模型.工业实验表明所提出两阶段优化建模方法在求解速度与求解精度均满足现场要求.Abstract: Steelmaking and continuous casting production scheduling is a multi-equipment assignment, multi-objective, multi-constraint, discrete and continuous variables hybrid optimization problem. Traditional modeling and solving methods are usually adopted to solve it, but they cannot meet the requirement in terms of high scheduling accuracy and fast problem solving speed. A new two-stage optimal modeling algorithm is proposed in this paper. In stage one, we show that minimizing the waiting time from steelmaking to continuous casting is equivalent to maximizing the converter operating time at first. Then we built a multiple-stage dynamic programming equation and optimization model using discrete variables, with the goal of maximizing the converter operating time. In stage two, we establish a linear programming conflict elimination model using continuous variables by converting a non-linear performance index into two equavalent linear optimization indexes including lead time, lag time between pratical casting and planned casting, and combining the other two indexes including time gap between furnaces on same caster and waiting duration for steel ladle among converters, refining furnaces and casters. On-site industry application validates that the proposed method can solve the scheduling problem with high speed and accuracy.
-
近年来,随着社交网络和电子商务的飞速发展,微博、Twitter、即时信息、商品评价等短文本形式的文字充斥着互联网.这些短文本包含了用户的潜在需求、兴趣点、意图倾向等,如何能够从这些短文本中获取信息从而更好地为用户提供服务成为关键.然而,这些短文本通常都有长度限制,如微博字数限制在140字以内,短消息限制在70字以内,如何能够从只言片语中挖掘出目标信息成为了一大挑战.在使用传统的向量空间模型 (Vector space model,VSM)将短文本数字向量化时,该向量会很稀疏[1],特别是在测试阶段,由于训练数据的不充分,会造成很多有用特征因未被模型捕获过而被忽略的情况,因此使用传统的文本分类方法将导致分类结果不理想.
为了充分利用短文本所蕴含的信息,已有很多相关研究.一种方案是计算短文本之间的相似性,文献[2]提出使用外部数据作为一个桥梁,如果预测文档和训练文档同时和某一外部文档相似,那么领域标签信息也应该一样,但搜集的外部数据必须和实验数据相关;文献[3]提出使用搜索引擎返回的结果来衡量两个词语之间的相似度,但是需要等待搜索引擎返回结果,比较耗时,不利于在线实时应用;文献[4]提出使用固定的资源维基百科作为知识库进行搜索.另一种解决方案是在短文本稀疏特征的基础上扩展相关语义特征,文献[5]提出使用Lucene[6]对维基百科建立索引,在原有特征基础上增加Lucene返回的搜索结果作为额外特征;文献[7]提出使用短文本隐藏的主题作为额外特征集,在相关数据上使用LDA(Latent Dirichlet allocation)[8]获得主题模型,针对短文本首先进行推理得到主题特征,与原始特征融合用于训练和分类.上述研究都是基于利用外部相关数据对原始文本进行相似度估计或者特征扩展,并且取得了不错的效果,但是对外部数据的相关性要求较高,而这些相关数据通常是根据领域知识,人工干预下进行收集的,在实际应用中获取相关领域的外部数据有时比较困难.上述方法最终将文本转换为空间向量,统计特征的共现权重,简单来说是一种计数原理.随着神经网络模型在自然语言处理中的广泛应用,文献[9]提出将词矢量作为输入特征,利用卷积神经网络进行模型训练.为了得到句子层级的矢量表示,文献[10]提出将变长文本训练为固定维度的段落矢量(Paragraph vector)的概念,文献[11]提出动态卷积神经网络,不依赖于句法解析树,而是利用动态k-max pooling提取全局特征.
基于文献[7],为了摆脱对外部相关数据的过度依赖,本文从句子语义层面出发,深度挖掘短文本所表达的语义.本文利用词矢量作为输入特征表征语义.词矢量是指将词语映射成空间中的一个低维实数向量,向量之间的距离描述了词与词之间的语义关系,语义相近的词语在空间中成群出现,提高了文字表示的泛化能力.为了更好地利用词矢量,本文提出了概率语义分布模型,利用词矢量来表征语义分布,在一定程度上避免了数据的稀疏性问题,实验结果表明,本文所提出的方法准确率相对于传统的分类器提高了17.7%.
本文结构如下:第1节简要介绍连续空间词矢量,第2节描述了本文提出的概率语义分布模型,第3节介绍了在概率语义分布模型的假设下,本文提出了一种基于通用语义背景模型的短文本分类方法,第4节为实验及结果分析,第5节给出总结.
1. 连续空间词矢量
近几年,越来越多的学者开始关注利用低维实数向量来表征一个词、短语或者句子.例如,LSA (Latent semantic analysis)[12]和 LDA模型将文本映射成主题模型里的一个低维向量.随着神经网络的广泛应用,人们可以利用神经网络对大规模语料进行语言模型训练,同时能够得到描述语义和句法关系的词矢量.其中,文献[13]提出的Skip-gram模型便是一种能够高效得到词矢量的训练模型,通过训练无标注语料将每个词映射成低维实数向量,每一维都代表了词的浅层语义特征[14].同时,文献[15]发现上述模型训练得到的词矢量能够通过余弦距离描述词与词之间的语义和句法关系,并且相同的余弦距离表征了同样关系,例如,向量"Man"与向量"King"之间的距离近似于向量"Woman"与向量"Queen"之间的距离.因此,本文利用词矢量上述特性,结合短文本的特点,提出了概率语义分布模型,应用于短文本分类中.
2. 概率语义分布模型
不同于传统的文本分类算法,本文认为短文本是在贝叶斯框架下各个领域里的一个抽样.本文假设短文本数据产生于一个概率语义分布模型,不同领域数据来自于不同的语义分布模型,并且我们可以利用已知的文本数据去估计这些模型.得到这些模型之后,对于新的测试数据,计算来源于各个模型的概率,根据贝叶斯原理选择类别标签作为预测结果.
假设训练数据包含一系列的短文本文档,D={d1,d2, $d_3,\cdots,d_n$ },di表示一条短文本,共n条训练数据,分别属于C={c1,c2, $c_3,\cdots,c_m$ },cj为领域标记,共m个领域.本文假设同一领域短文本文档产生于同一个语义分布模型(模型参数为λ).一条短文本数据di的产生,首先根据先验概率p(cj|λ)选择语义分布模型,然后根据该领域模型的模型参数p(di|cj;λ)产生文档di.因此文档di的产生概率为p(di|λ):
$p({{d}_{i}}|\lambda )=\sum\limits_{j=1}^{m}{p}({{c}_{j}}|\text{ }\lambda )p({{d}_{i}}|{{c}_{j}};\lambda )$
(1) 类似于一元语言模型,认为短文本中词与词之间是互相独立的,不依赖于前文信息,dik表示短文本di中位置为k的单词,|di| 表示文本中单词的个数,则有
$p({{d}_{i}}|{{c}_{j}};\text{ }\lambda )=\prod\limits_{k=1}^{|{{d}_{i}}|}{p}({{d}_{ik}}|{{c}_{j}};\text{ }\lambda )$
(2) 假设已通过训练数据计算得到模型参数 $\widehat{\text{ }\lambda }$ ,针对测试数据,可以分别计算各个分布模型产生该数据的概率.根据贝叶斯原理,由式(1) 和(2) 得到
$\begin{array}{*{35}{l}} p({{c}_{j}}|{{d}_{i}};\hat{\lambda }) & =\frac{p({{c}_{j}}|\hat{\lambda })p({{d}_{i}}|{{c}_{j}};\hat{\lambda })}{p({{d}_{i}}|\hat{\lambda })}=\text{ } \\ {} & \frac{p({{c}_{j}}|\hat{\lambda })\prod\limits_{k=1}^{|{{d}_{i}}|}{p}({{d}_{ik}}|{{c}_{j}};\hat{\lambda })}{\sum\limits_{l=1}^{|C|}{p}({{c}_{l}}|\hat{\lambda })\prod\limits_{k=1}^{|{{d}_{i}}|}{p}({{d}_{ik}}|{{c}_{l}};\hat{\lambda })}\text{ } \\ \end{array}$
(3) 根据上述提出的概率语义分布模型假设,本文认为可以选择合适的模型去近似描述每个领域内的词语分布.由于混合高斯模型能够描述任意形状的概率分布,因此本文选用混合高斯模型.由于训练数据的不充分,直接使用混合高斯模型进行多高斯训练时会产生欠拟合,因此本文在混合高斯模型的基础上提出了一种基于通用语义背景模型的短文本分类方法.
3. 基于通用语义背景模型的短文本分类
在实际应用中,由于自然语言表达的灵活性,获取足够多的标注数据是一件费时费力的事情,如何能够充分利用已有数据进行短文本分类成为关键.在图像处理、说话人识别系统中,高斯混合-通用背景模型[16-17]便是一种能够在训练数据不足的情况下,由一个通用的背景模型根据少量的训练数据自适应到目标模型上,并且取得了很好效果.因此,借鉴于高斯混合-通用背景模型,在概率语义分布模型的假设下,首先利用混合高斯构建通用概率语义背景分布模型,然后根据训练数据自适应得到目标领域概率语义分布模型,如图 1所示.
图 1 基于通用语义背景模型的短文本分类Fig. 1 Short text classification based on universal semantic background model3.1 词汇特征
在连续空间词矢量表示中,通过向量之间的空间距离来表征词与词之间的特定关系,并且文献[18]指出从大量无标记文本数据训练得到的词矢量要比随机初始化的矢量性能要好.在短文本分类中,我们应该首先训练得到词矢量.然而,词矢量的训练通常需要耗费很长时间,并且已有许多学者将训练好的词矢量进行了开源.本文的实验直接使用文献[19]提供的词矢量词典,该词典是利用大概十亿单词数量的谷歌新闻数据训练得到的维度为300的词矢量.
3.2 高斯混合模型
高斯混合模型(Gaussian mixture model,GMM)作为一种通用的概率模型,只要高斯数足够大,便能有效地模拟多维矢量的连续概率分布,因而很适合去表征语义分布.高斯混合模型是一系列高斯分布的加权组合.一个由M个高斯分量组成的高斯混合密度函数是M个高斯密度函数的线性加权和:
$p({{d}_{i}}|\lambda )=\sum\limits_{k=1}^{M}{{{w}_{k}}}{{p}_{k}}({{d}_{i}})\text{ }$
(4) 上式中 λ 为GMM模型参数,pk(di), $k = 1,\cdots,M$ 是高斯分量密度函数. wk, $k = 1,\cdots,M$ 是各个高斯分量的权重,满足 $\sum_{k=1}^{M} w_k=1$ .每个高斯分量的概率密度函数公式 $p_k(d_i)$ 表示如下:
$\frac{1}{{{(2\pi )}^{\frac{D}{2}}}|{{\Sigma }_{k}}{{|}^{\frac{1}{2}}}}\text{exp}\{-\frac{1}{2}{{({{d}_{i}}-{{\mu }_{k}})}^{\text{T}}}\Sigma _{k}^{-1}({{d}_{i}}-{{\mu }_{k}})\}\text{ }$
(5) 这里 $\mu_k$ 是第k个高斯分量的均值矢量, $\Sigma_k$ 为相应的协方差矩阵,D是特征矢量的维度. 这样,GMM模型便可以由以下参数集合表示:
$\lambda =\{{{w}_{k}},{{\mu }_{k}},{{\Sigma }_{k}}\},\quad k=1,2,\cdots ,M$
(6) 使用GMM对概率语义分布建模主要基于两个出发点: 1) GMM的高斯分量能够描述一定词矢量的分布; 2) 线性加权的高斯密度函数可以逼近任意形状的概率分布,因此选用GMM对语义分布进行描述.
3.3 最大后验模型自适应
利用高斯混合模型在无标注文本数据上训练得到通用概率语义背景分布模型,再用带有标记的训练数据进行模型自适应得到目标模型.最大后验概率(Maximum a posteriori,MAP)是一种典型的贝叶斯估计,它首先计算训练数据相对于通用背景模型的各个统计量,然后用一个相关系数将通用背景模型参数与相关统计量联合,得到目标模型.给定通用背景模型: $\lambda = \{w_k,\mu_k,\Sigma_k \},~k = 1,2,\cdots,M$ ,以及某一特定领域内的短文本训练数据 $D_{c_j}=\{d_{c_1},\cdots,d_{c_i},\cdots,d_{|c_j|} \}$ ,对每一条训练数据计算其在各高斯分量上的占有率,即后验条件概率:
\begin{equation}p(k|d_{c_i}) =\frac{w_kp_k(d_{c_i})}{\sum\limits_{j=1}^{M}w_jp_j(d_{c_i})}\end{equation}
(7) 然后便可计算出与权重相关的零阶统计量nk,与均值相关的一阶统计量 $E_k(d)$ 以及与协方差矩阵相关的二阶统计量 $E_k(d^2) $ :
\begin{equation}n_k = \sum_{c_i=1}^{|c_j|}p(k|d_{c_i}) \end{equation}
(8) \begin{equation}E_k(d) = \frac{1}{n_k}\sum_{c_i=1}^{|c_j|}d_{c_i}p(k|d_{c_i})\end{equation}
(9) \begin{equation}E_k(d^2) = \frac{1}{n_k}\sum_{c_i=1}^{|c_j|}d_{c_i}^2p(k|d_{c_i})\end{equation}
(10) 用以上计算得到的统计量对通用背景模型的各个高斯分量的权重、均值和协方差进行自适应,得到新的模型参数:
\begin{equation}w_k^* = \left[\frac{\alpha_k^wn_k}{T}+(1-\alpha_k^w)w_k\right]\gamma \end{equation}
(11) \begin{equation}\mu_k^* = \alpha_k^mE_k(d)+(1-\alpha_k^m)\mu_k \end{equation}
(12) \begin{equation}\sigma_k^{2*} = \alpha_k^\nu E_k(d^2) +(1-\alpha_k^\nu)(\sigma_k^2+\mu_k^2) -(\mu_k^*)^2 \end{equation}
(13) 其中 $\gamma$ 用来平衡高斯分量的权值,以保证更新后各分量的权值和为1. $\{\alpha_k^w,\alpha_k^m,\alpha_k^\nu\ \}$ 是调整新旧模型参数平衡的自适应系数,通常使用同一个自适应系数.为了能够确定上述参数,本文在训练集上使用5折交叉验证来确保参数的可靠性.
4. 实验结果与分析
为了验证所提出方法的有效性,本文利用文献[7]提供的短文本数据,首先验证背景模型和高斯数对分类性能的影响,其次与基线系统进行比较,最后验证所提出的方法对训练数据的依赖性.
4.1 实验数据与评价标准
本文选择文献[7]提供的网页搜索片段数据作为实验数据,网页搜索片段数据集是将特定领域词送入谷歌搜索引擎得到的搜索结果片段,为了保证领域的特定性,通常选取前20~30个片段作为引用数据.例如计算机类,选取60个计算机领域的词语,分别送入谷歌搜索引擎,每次抽取搜索结果的前20条数据作为训练数据,则可以得到1200条数据,数据分布如表 1.为了区分训练数据和测试数据,在生成测试数据时所使用的领域词不同于训练数据.如表 2所示,无论是英文单词未经提取词干还是经过提取词干(Porter stemming)[20]之后,都会有超过40%的未登录词(未登录词通常是指未在词典中出现的词[21])出现在测试集中,这极大地增加了分类的难度.
表 1 网页搜索片段数据分布Table 1 Statistics of web snippets data编号 领域 训练数据 测试数据 1 商业 1200 300 2 计算机 1200 300 3 文化与艺术 1880 330 4 教育与科技 2360 300 5 技术 220 150 6 健康 880 300 7 社会政策 1200 300 8 体育 1120 300 共计 10060 2280 表 2 未登录词分布Table 2 Statistics of unseen words原始单词 词干 训练数据 26 265 21 596 测试数据 10 037 8 200 未登录词 4 378 3 677 未登录词的比例 43.62% 44.84% 在实验过程中,本文使用精度(Precision,P)、召回率(Recall,R)、F1值和准确率(Accuracy,A)作为评价标准.
4.2 实验
4.2.1 参数设置
如何选择背景数据进行通用背景语义模型训练以及不同的背景模型对性能如何影响,混合高斯模型中的高斯数如何确定,这些参数都需要通过实验进行验证.本文选择: 1) 相关数据:去掉标注的训练数据作为背景数据;2) 通用数据:选取语言资源联盟 (Linguistic Data Consortium)提供的新闻数据[22],本文仅选取标签 Headline下的文本;3) 混合数据:相关数据和通用数据的混合,分别作为背景数据进行背景模型训练,实验结果如图 2所示.
当我们不断增加高斯数时,混合高斯能够很好地拟合特征分布,但是当高斯数过高时,由于数据的稀缺,会出现过拟合现象,正如图 2中当使用训练数据1) 进行背景模型训练时,高斯数达到256时无法拟合出混合高斯模型.在图 2中,直接使用无标注的训练数据进行通用背景模型训练,在低维混合高斯下能够快速地提高分类性能,但是由于数据有限,无法进行高维高斯拟合,高斯数为128时准确率达到78.6%;使用通用数据,由于数据量较大,能够进行高维高斯拟合,并且在高维混合高斯的情况下能够达到直接使用训练数据的分类性能,高斯数为8时准确率达到最高75.83%;当使用无标注的训练数据+通用数据时,高斯数为16,短文本分类准确率达到最高值80%.
4.2.2 与基线系统相比
为了验证本文所提方法的有效性,本文选择以下方法作为基线系统:
1) TF*IDF + SVM/MaxEnt:特征值采用TF*IDF进行计算,利用支持向量机(Support vector machine,SVM)或最大熵(MaxEnt)作为分类器.
2) LDA + MaxEnt:在文献[7]中,利用LDA对文本进行主题特征提取,与文本特征进行合并,利用MaxEnt进行分类模型的训练.
3) Wiki feature+SVM: 对维基百科数据1进行去除网页标签、网页链接等预处理之后,使用Lucene对其建立索引,对每一条短文本实验数据进行检索.在检索结果中,类似文献[5]中提出的方法,将维基百科数据的标题作为额外的文本特征扩充到原始短文本数据中.不同于文献[5]中所描述的聚类任务,我们将融合后的文本用于短文本分类.
1http://download.wikipedia.com/enwiki
4) Paragraph vector +SVM:文献[10]提出了一种无监督的方法,利用定长数学向量表征不定长文本.该模型认为当前词语的选择不仅由上下文决定,还由隐藏的文本矢量共同决定.该隐藏文本矢量可以看做为文本的隐藏主题[23].
5) LSTM (Long short term memory):对文献[24]中提出的LSTM模型进行修改,组成结构为单一的LSTM层、均值池化层(Average pooling layer)和 逻辑回归层(Logistic regression layer),使其能够进行文本类别预测[23].
在传统的文本分类方法中,通常是利用词袋模型(Bag of words,BoW)将文本离散化,计算特征权重,转换为向量空间模型中的特征权重向量,每个词被转换为字典中的索引数字.这种方法降低了计算复杂度,但是对于未登录词的处理能力大幅度降低.
由于在训练的过程中,分类模型未捕捉到未登录词对分类结果的贡献能力,在测试阶段,未登录词通常会被忽略.尤其是在该测试集中会出现超过40%的未登录词,这极大地增加了分类难度.因此,在表 3中传统的文本分类方法SVM和MaxEnt性能均不是很高.以维基百科作为搜索库,利用Lucene的搜索结果进行原始短文本扩展,在一定程度上降低了特征稀疏性,对分类性能有所提升.本文的方法利用词矢量将文本向量化,词矢量体现了一定的语言泛化能力,充分利用了训练数据里的每一个有用词语,使得准确率相对传统方法提高了17.7%,并且如表 4所示每一领域的分类结果 F1 值均优于传统的分类结果.在Paragraph vector和LSTM这两种模型中,都使用到了词矢量,但都未能有效地捕获到语句中的语义信息.
表 3 与基线系统对比实验结果(%)Table 3 Experimental results of the proposed method against other methods (%)方法 Accuracy TF*IDF+SVM 66.14 TF*IDF+MaxEnt 66.80 LDA+MaxEnt 82.18 Wiki feature+SVM 76.89 Paragraph vector+SVM 61.90 LSTM 63.00 本文的方法 80.00 文献[7]提到的方法需要根据领域知识额外准备大概470000篇维基百科数据,共计3.5GB的相关数据进行主题模型训练,增加了收集数据的难度.本文在使用混合数据时准确率达到80%,略低于文献[7]中的82.18%,但是本文有效地避免了收集相关数据的困难.本文选用维基百科数据,对其进行去除网页标签、链接等预处理之后,用于LDA主题模型训练和词矢量训练.在主题模型训练过程中,主题数目选择为50、100、200、300、400等,在训练集上利用五折交叉验证确定最优主题数.针对词矢量的训练,使用开源工具 word2vector2训练得到维度为300的词矢量.在使用相同外部数据的情况下,本文方法取得79.93%的性能,略高于基于LDA+MaxEnt方法的79.89%.从这一点可以看出,在使用外部数据进行主题模型训练时,外部数据与实验数据的相关性,是影响主题特征贡献能力的一个重要因素.因此,当面对一个新的分类任务时,文献[7]中的方法需要根据领域知识重新挑选大量相关语料进行主题模型训练,从一定程度来讲,本文的方法更易实现.
2http://word2vec.googlecode.com/svn/trunk
表 4 SVM、MaxEnt和本文方法的实验结果Table 4 Evaluations of SVM,MaxEnt and the proposed methodSVM MaxEnt 本文的方法 领域 P (%) R (%) F1 P (%) R (%) F1 P (%) R (%) F1 社会政策 77.61 52.00 0.6228 70.75 50.00 0.5859 86.36 70.37 0.7755 计算机 73.75 63.67 0.6834 72.26 66.00 0.6899 80.31 87.29 0.8365 教育与科技 41.98 82.00 0.5553 45.93 82.67 0.5905 81.60 68.23 0.7432 体育 85.19 76.67 0.8070 86.08 78.33 0.8202 84.54 89.93 0.8715 健康 89.01 56.67 0.6925 86.94 64.33 0.7395 76.35 85.57 0.8070 技术 76.53 50.00 0.6048 72.84 39.33 0.5108 58.82 93.33 0.7216 商业 70.37 57.00 0.6298 68.05 60.33 0.6396 73.99 67.33 0.7051 文化与艺术 62.27 81.52 0.7060 62.86 78.48 0.6981 88.15 77.85 0.8268 4.2.3 训练数据大小对分类效果的影响
为了验证本文方法对训练数据的依赖性,本文将训练数据保持原领域数据的分布比例不变平均分成10份,每次增加1份进行试验,在同一测试集上进行测试,得到10组实验结果,如图 3所示.由于SVM和MaxEnt的分类效果相差不大,因此仅选择了MaxEnt作为基线系统.随着训练数据的减少,测试集中未登录词的比重会逐渐加大,MaxEnt的分类效果变化幅度较大,对训练数据的依赖性比较大.在训练数据稀缺的情况下(仅占原训练数据的1/10) ,本文方法能够将正确率从47.06%提高到71.54% (相对提高52%).从另一角度说明如何充分利用词汇信息成为分类的关键,而这也是本文方法的关键.
为了进一步检验训练数据对本文方法的影响,本文继续将训练数据数量缩小,如图 4所示.在仅有100条训练数据的情况下,本文所提出的方法准确率能够达到51.4%,高于MaxEnt在1000条训练数据下的47.06%,这对于获取训练数据比较困难的应用来说,可以大大地降低对训练数据的依赖性.
5. 结论
本文摒弃了传统的文本向量空间表示模型,提出概率语义分布模型,认为短文本是来自于概率语义模型的一个抽样,利用词矢量将文本数字化,通过无标记数据构建通用语义背景模型,利用训练数据进行自适应得到目标模型.实验结果验证了本文所提出方法的可行性,利用能够表征语义和句法关系的词矢量有效地降低了训练数据不充分所带来的影响,短文本分类性能明显优于传统的文本分类方法,降低了对训练数据的依赖性.虽然本文的实验结果略低于基于主题模型的短文本分类系统的结果,但明显优于基于SVM和最大熵的分类算法,并且本文的方法无需准备大量的相关数据,在一定程度上本文方法更易实现.
-
图 2 基于动态规划10个炉次的粗调度甘特图
Fig. 2 Gantt chart of ten charges rough scheduling based on dynamic programming
图 3 10个炉次冲突解消后的调度甘特图
Fig. 3 Scheduling Gantt chart after ten charges machine conflicts eliminated
i 浇次序号,i = 1,2,3, $\cdots,N$ ; Ni 第i个浇次中的炉次数; j 炉次序号,j = 1,2,...,Ni; Lij 第i个浇次的第j个炉次; $\vartheta_{ij}$ 炉次Lij从转炉到连铸工序的加工设 备总数; 浇次计划中的精炼方式确定后, $\vartheta_{ij}$ 的取值就确定了; θ 炉次Lij从转炉到连铸加工的顺序号, θ = 1,2,..., $\vartheta_{ij}$ ; g 表示设备类,g = 1,2,3,...,G,如g = 1表示转炉设备; $g = 2$ 表示第一类 精炼设备类, $g = G$ 表示连铸设备类; Ti 浇次i的理想开浇时间,由现场给定; Mg 表示第g类设备中含有的并行机数; kg 设备变量,表示g类设备的第k个设 备序号; kg = 1,2,3 $,\cdots$ ,Mg; Tij( $k_{g(\theta)})$ 炉次Lij的第θ个操作在第g类设备的 第 $k_{g(\theta)}$ 个设备上的加工时间;当θ不 同时,炉次Lij的操作设备类型g也不 同,所以,g是θ的函数,即g = $g(\theta)$ , kg = $k_{g(\theta)}$ ;对于连铸设备,不同炉次在 连铸机的处理时间是不尽相同的.所以, 处理时间Tij( $k_{g(\theta)}$ )是设备变量 $k_{g(\theta)}$ 的函数; Tij( $k_{g(\theta)}$ , $k_{g(\theta+1) }$ ) 炉次Lij从第θ个操作设备 $k_{g(\theta)}$ 到第 $\theta+1$ 个操作设备 $k_{g(\theta+1) }$ 之间的运输时 间.由于炉次Lij的第θ和 $\theta+1$ 个操 作设备不同,其运输时间也不尽相同,所 以运输时间Tij( $k_{g(\theta)}$ , $k_{g(\theta+1) }$ )是炉次上 下操作设备的函数; yij( $k_{g(\theta)}$ ) 设备变量 $k_{g(\theta)}$ 的函数,当yij( $k_{g(\theta)}$ ) = 1,表示炉次Lij的第θ个操作在g类设 备上的第 $k_{g(\theta)}$ 个设备上加工;否则, yij( $k_{g(\theta)}$ ) = 0; xij( $k_{g(\theta)}$ ) 称为时间变量.炉次Lij的第θ个操作在 第g类设备的第 $k_{g(\theta)}$ 个机器上加工的开始时间. 
下载: 导出CSV
表 1 三个浇次10个炉次计划的初始数据
Table 1 Initial data of three cast including ten charges
浇次号 炉次号 制造命令号 钢号 精炼方式 浇铸目的地 1 115578 DV3943D1 R 1#CC 1 2 115579 DT0192D1 R 1#CC 3 115580 DV3948D1 R 1#CC 4 115769 DT0138D1 R 1#CC 5 118275 AP0740D5 C 2#CC 2 6 118277 AP0740D5 C 2#CC 7 118281 DV3943D1 R 2#CC 8 461348 DV3943D1 R 3#CC 3 9 461349 DV3943D1 R 3#CC 10 461350 DV3943D1 RK 3#CC
下载: 导出CSV
表 2 基于动态规划的设备指派结果
Table 2 Equipment assignment base on dynamic programming
浇次号 炉次号 设备指派结果 设备处理时间 运输时间(分钟) 1 1 2#LD-1#RH-1#CC 35,36,48 8,14 2 2#LD-1#RH-1#CC 35,36,39 8,14 3 2#LD-1#RH-1#CC 35,36,52 8,14 4 2#LD-1#RH-1#CC 35,36,45 8,14 5 3#LD-1#CAS-2#CC 35,30,49 9,12 2 6 3#LD-1#CAS-2#CC 35,30,61 9,12 7 3#LD-2#RH-2#CC 35,36,42 9,15 8 1#LD-3#RH-3#CC 35,36,64 8,20 3 9 1#LD-3#RH-3#CC 35,36,64 8,20 10 1#LD-3#RH-KIP-3#CC 35,36,25,43 8,9,19
下载: 导出CSV
表 3 基于动态规划的10个炉次粗调度时刻表
Table 3 Ten charges rough schedule base on dynamic programming
炉次号 转炉 精炼1 精炼2 连铸 始 末 始 末 始 末 始 末 1 5:44 6:19 6:27 7:03 - - 7:17 8:05 2 6:32 7:07 7:15 7:51 - - 8:05 8:44 3 7:11 7:46 7:54 8:30 - - 8:44 9:36 4 8:03 8:38 8:46 9:22 - - 9:36 10:21 5 5:44 6:19 6:28 6:58 - - 7:10 7:59 6 6:33 7:08 7:17 7:47 - - 7:59 9:00 7 7:25 8:00 8:09 8:45 - - 9:00 9:42 8 5:46 6:21 6:29 7:05 - - 7:25 8:29 9 6:50 7:25 7:33 8:09 - - 8:29 9:33 10 7:21 7:56 8:04 8:40 8:49 9:14 9:33 10:16
下载: 导出CSV
表 4 10 个炉次机器冲突解消后的调度表
Table 4 Ten charges schedule table after conflicts eliminated
炉次号 转炉 精炼1 精炼2 连铸 始 末 始 末 始 末 始 末 1 5:44 6:19 6:27 7:03 - - 7:17 8:05 2 6:32 7:07 7:15 7:51 - - 8:05 8:44 3 7:11 7:46 7:54 8:30 - - 8:44 9:36 4 8:03 8:38 8:46 9:22 - - 9:36 10:21 5 5:44 6:19 6:28 6:58 - - 7:10 7:59 6 6:33 7:08 7:17 7:47 - - 7:59 9:00 7 7:25 8:00 8:09 8:45 - - 9:00 9:42 8 5:46 6:21 6:29 7:05 - - 7:25 8:29 9 6:45 7:20 7:28 8:04 - - 8:29 9:33 10 7:21 7:56 8:04 8:40 8:49 9:14 9:33 10:16
下载: 导出CSV
-
[1] 吴启迪, 乔非, 李莉, 吴莹. 基于数据的复杂制造过程调度. 自动化学报, 2009, 35(6): 807-813 doi: 10.3724/SP.J.1004.2009.00807Wu Qi-Di, Qiao Fei, Li Li, Wu Ying. Data-based scheduling for complex manufacturing processes. Acta Automatica Sinica, 2009, 35(6): 807-813 doi: 10.3724/SP.J.1004.2009.00807 [2] 王秀英, 柴天佑, 郑秉霖. 炼钢—连铸智能调度软件的开发及应用. 计算机集成制造系统, 2006, 12(8): 1220-1226 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ200608010.htmWang Xiu-Ying, Chai Tian-You, Zheng Bing-Lin. Intelligent scheduling software & its application in steelmaking and continuous casting. Computer Integrated Manufacturing Systems, 2006, 12(8): 1220-1226 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ200608010.htm [3] Missbauer H, Hauber W, Stadler W. A scheduling system for the steelmaking-continuous casting process. A case study from the steel-making industry. International Journal of Production Research, 2009, 47(15): 4147-4172 [4] Pacciarelli D, Pranzo M. Production scheduling in a steelmaking-continuous casting plant. Computers and Chemical Engineering, 2004, 28(12): 2823-2835 doi: 10.1016/j.compchemeng.2004.08.031 [5] 黄敏, 付亚平, 王洪峰, 朱兵虎, 王兴伟. 设备带有恶化特性的作业车间调度模型与算法. 自动化学报, 2015, 41(3): 551-558 http://www.aas.net.cn/CN/abstract/abstract18633.shtmlHuang Min, Fu Ya-Ping, Wang Hong-Feng, Zhu Bing-Hu, Wang Xing-Wei. Job-shop scheduling model and algorithm with machine deterioration. Acta Automatica Sinica, 2015, 41(3): 551-558 http://www.aas.net.cn/CN/abstract/abstract18633.shtml [6] Bellabdaoui A, Teghem J. A mixed-integer linear programming model for the continuous casting planning. International Journal of Production Economics, 2006, 104(2): 260-270 doi: 10.1016/j.ijpe.2004.10.016 [7] Mao K, Pan Q K, Pang X F, Chai T Y. A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process. European Journal of Operational Research, 2014, 236(1): 51-60 doi: 10.1016/j.ejor.2013.11.010 [8] Tang L X, Zhao Y, Liu J Y. An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production. IEEE Transactions on Evolutionary Computation, 2014, 18(2): 209-225 doi: 10.1109/TEVC.2013.2250977 [9] Sbihi A, Bellabdaoui A, Teghem J. Solving a mixed integer linear program with times setup for the steel-continuous casting planning and scheduling problem. International Journal of Production Research, 2014, 52(24): 7276-7296 doi: 10.1080/00207543.2014.919421 [10] 俞胜平, 柴天佑. 开工时间延迟下的炼钢—连铸生产重调度方法. 自动化学报, 2016, 42(3): 358-374 http://www.aas.net.cn/CN/abstract/abstract18826.shtmlYu Sheng-Ping, Chai Tian-You. Rescheduling method for starting time delay in steelmaking and continuous casting production processes. Acta Automatica Sinica, 2016, 42(3): 358-374 http://www.aas.net.cn/CN/abstract/abstract18826.shtml [11] Tan Y Y, Liu S X. Models and optimisation approaches for scheduling steelmaking-refining-continuous casting production under variable electricity price. International Journal of Production Research, 2014, 52(4): 1032-1049 doi: 10.1080/00207543.2013.828179 [12] 李铁克, 苏志雄. 炼钢连铸生产调度问题的两阶段遗传算法. 中国管理科学, 2009, 17(5): 68-74 http://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK200905010.htmLi Tie-Ke, Su Zhi-Xiong. Two-stage genetic algorithm for SM-CC production scheduling. Chinese Journal of Management Science, 2009, 17(5): 68-74 http://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK200905010.htm [13] Atighehchian A, Bijari M, Tarkesh H. A novel hybrid algorithm for scheduling steel-making continuous casting production. Computers & Operations Research, 2009, 36(8): 2450-2461 http://cn.bing.com/academic/profile?id=2060539563&encoded=0&v=paper_preview&mkt=zh-cn [14] Pan L, Yu S P, Zheng B L, Chai T Y. Cast batch planning for steelmaking and continuous casting based on ant colony algorithm. In: Proceedings of the 2010 International Symposium on Computational Intelligence and Design. Hangzhou, China: IEEE, 2010. 244-247 [15] Li J Q, Pan Q K, Mao K, Suganthan P N. Solving the steelmaking casting problem using an effective fruit fly optimisation algorithm. Knowledge-Based Systems, 2014, 72: 28-36 doi: 10.1016/j.knosys.2014.08.022 [16] Pan Q K. An effective co-evolutionary artificial bee colony algorithm for steelmaking-continuous casting scheduling. European Journal of Operational Research, 2016, 250(3): 702-714 doi: 10.1016/j.ejor.2015.10.007 [17] Wang X Y, Jiang X J, Wang H H. Optimal modeling and analysis of steelmaking and continuous casting production scheduling. In: Proceedings of the 11th World Congress on Intelligent Control and Automation. Shenyang, China: IEEE, 2014. 5057-5062 [18] 王秀英. 炼钢—连铸混合优化调度方法及应用[博士学位论文], 东北大学, 中国, 2012Wang Xiu-Ying. Hybrid Optimization Scheduling Method of Steelmaking and Continuous Casting and its Application [Ph.D. dissertation], Northeastern University, China, 2012 [19] 王秀英, 柴天佑, 郑秉霖. 炼钢—连铸调度模型参数优化设定方法. 系统工程学报, 2011, 26(4): 531-537 http://www.cnki.com.cn/Article/CJFDTOTAL-XTGC201104015.htmWang Xiu-Ying, Chai Tian-You, Zheng Bing-Lin. Parameter optimization setting of steel making and continuous casting scheduling model. Journal of Systems Science and Systems Engineering, 2011, 26(4): 531-537 http://www.cnki.com.cn/Article/CJFDTOTAL-XTGC201104015.htm -
下载:
计量
- 文章访问数: 1881
- HTML全文浏览量: 168
- PDF下载量: 923
- 被引次数: 0
