- 在线时间
- 1273 小时
- 最后登录
- 2025-7-28
- 注册时间
- 2022-2-27
- 听众数
- 33
- 收听数
- 0
- 能力
- 90 分
- 体力
- 171731 点
- 威望
- 9 点
- 阅读权限
- 255
- 积分
- 54650
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1814
- 主题
- 1195
- 精华
- 33
- 分享
- 0
- 好友
- 35
TA的每日心情 | 开心 2025-7-18 09:36 |
---|
签到天数: 616 天 [LV.9]以坛为家II 网络挑战赛参赛者 - 自我介绍
- 我是普大帝,拼搏奋进,一往无前。
 |
你好!我是陪你一起进阶人生的普大帝!愿你成才!祝你成长!
3 ]" k% j6 q+ I+ v为大家更新一些算法类的辅助资料,大家在想学习时,或者比赛急需时就可以按照对应的名字找到对应的算法,加以应用了。大家按照下图所示箭头处点击主题,就可以查看到其他算法类内容了,或者搜索框内输入算法大全,也可以搜索到对应的贴子,本篇为第32篇。
+ R5 i: q. l r" K, M* f$ r![]()
) s# s i9 X9 i. h, ~- X作业计划
0 T9 R }; Q* ?1 B$ J, ~! d9 l排序的理论与方法是编制车间作业计划的基础。本章将介绍排序问题的基本概念,重点介绍流水作业排序问题。2 Y; p. p9 v) |) R
§1 流水车间调度问题
+ `( u1 k4 G, J- e5 |- m0 G; g1.1 排序问题的基本概念
7 Z, _2 \3 i V4 `' E5 L& X7 E; {+ z1.1.1 名词术语在生产管理中,常用到“编制作业计划”(Scheduling)、“排序”(Sequencing)、“派工”(Dispatching) 、“控制”(Controlling)和“赶工”(Expediting)这些名词。一般说来,编制作业计划与排序不是同义语。排序只是确定工件在机器上的加工顺序。而编制作业计划,则不仅包括确定工件的加工顺序,而且还包括确定机器加工每个工件的开始时间和完成时间。因此,只有作业计划才能指导每个工人的生产活动。由于编制作业计划的主要问题是确定各台机器上工件的加工顺序,而且,在通常情况下都是按最早可能开(完)工时间来编排作计划的。因此,当工件的加工顺序确定之后,作业计划也就确定了。所以,人们常常不加区别地使用“排序”与“编制作业计划”这两个术语。在本章里,讲排序的时候就暗指相应的作业计划是最早时间作业计划。只有在需要的时候,才将这两个术语区别使用。“派工”是按作业计划的要求,将具体生产任务安排到具体的机床上加工,属于我们经常说的“调度”范围。“赶工”是在实际进度已落后于计划进度时采取的行动,也属于“调度”范围。“调度”是实行控制所采取的行动。“编制作业计划”是加工制造发生之前的活动;“调度”是在加工制造发生之后的活动。调度的依据是作业计划。比如,火车时刻表是一种作业计划,火车发生晚点,就要进行调度。调度是一种现场指挥。描述排序问题的名词术语来自加工制造行业。为了和惯用的名词术语保持一致,本书仍使用“机器”、“工件”、“工序”和“加工时间”等术语来描述各种不同的排序问题。但要注意,它们已不限于本来的含义。这里所说的“机器”,可以是工厂里的各种机床,也可以是维修工人;可以是轮船要停靠的码头,也可以是电子计算机中央处理单元、存贮器和输入、输出单元。一句话,表示“服务者”;工件则代表“服务对象”。工件可以是单个零件,也可以是一批相同的零件。假定有 n 个工件要经过 m 台机器加工。“加工路线”是工件加工的工艺过程决定的,它是工件加工在技术上的约束。比如,某工件要经过车、铣、占、磨的路线加工,我们可以用M1 M2 M3 M4 来表示。L 来表示加工路线。“加工顺序”则表示每台机器加工 n 个工件的先后顺序,是排序要解决的问题。2 H4 {% g( O2 ?+ g% r
1.1.2 假设条件与符号说明为了便于分析研究,建立数学模型,有必要对排序问题提出一些假设条件。
6 o- E: g3 d, ~+ h① 一个工件不能同时在几台不同的机器上加工。
( t. H5 v/ u; D# N% F; B9 P% b/ B② 工件在加工过程中采取平行移动方式,即当上一道工序完工后,立即送下道工序加工。! I; c& k; \1 r6 d7 c+ s/ C
③ 不允许中断。当一个工件一旦开始加工,必须一直进行到完工,不得中途停止插入其它工件。
, \" \, Y9 E1 K S- v- @$ b④ 每道工序只在一台机器上完成。
3 F/ |$ N/ v& M5 w⑤ 工件数、机器数和加工时间已知,加工时间与加工顺序无关。
% s' \$ ~. i D. ?⑥ 每台机器一次只能加工一个工件。, C* x; I3 [" |1 j) M# K
4 J+ f5 y6 S( z A: ^$ \
9 w% w) Q( s* H3 c$ `2 y$ w5 e! s
1.1.3 排序问题的分类和表示法
) d. b- f0 y1 h; ~9 r# t/ H排序问题有不同的分类方法。最常用的分类方法是按机器、工件和目标函数的特征分类。按机器的种类和数量不同,可以分成单台机器的排序问题和多台机器的排序问题。对于多台机器的排序问题,按工件加工路线的特征,可以分成单件作业(Job-shop)排序问题和流水作业(Flow-shop) 排序问题。工件的加工路线不同,是单件作业排序问题的基本特征;而所有工件的加工路线完全相同,则是流水作业排序问题的基本特征。按工件到达车间的情况不同,可以分成静态的排序问题和动态的排序问题。当进行排序时,所有工件都已到达,可以一次对它们进行排序,这是静态的排序问题;若工件是陆续到达,要随时安排它们的加工顺序,这是动态的排序问题。按目标函数的性质不同,也可划分不同的排序问题。譬如,同是单台机器的排序,目标是使平均流程时间最短和目标是使误期完工工件数最少,实质上是两种不同的排序问题。按目标函数的情况,还可以划分为单目标排序问题与多目标排序问题。以往研究的排序问题,大都属于单目标排序问题,而对多目标排序问题则很少研究。0 C( l8 E$ c# C
另外,按参数的性质,可以划分为确定型排序问题与随机型排序问题。所谓确定型排序问题,指加工时间和其它有关参数是已知确定的量;而随机型排序问题的加工时间和有关参数为随机变量。这两种排序问题的解法本质上不同。
! h8 d, r: e' _. y( F3 V
; w6 ~$ T' X# o! B; t# P0 E5 v; ]0 n4 `2 f( B* ~5 O/ _+ l
|
zan
|