110t电弧炉废钢预热装置设计【开题报告中期课程毕业说明书论文CAD图外文翻译】
收藏
资源目录
压缩包内文档预览：(预览前20页/共47页)
编号：20421063
类型：共享资源
大小：76.57MB
格式：ZIP
上传时间：2019-06-30
上传人：小***
认证信息
个人认证
林**（实名认证）
福建
IP属地：福建
100
积分
- 关 键 词：
-
开题报告中期课程毕业说明书论文CAD图外文翻译
110t电弧炉废钢预热装置设计【开题报告中期课程毕业说明书论文CAD图外文翻译】
- 资源描述：
-
110t电弧炉废钢预热装置设计【开题报告中期课程毕业说明书论文CAD图外文翻译】,开题报告中期课程毕业说明书论文CAD图外文翻译,110t电弧炉废钢预热装置设计【开题报告中期课程毕业说明书论文CAD图外文翻译】
- 内容简介：
-
题目：110t电弧炉废钢预热装置设计撰写内容要求（可加页）：一、设计（论文）进展状况1. 在分析后，确定了预热装置的方案，以及输送装置的方案2.出装配图 图1 废钢预热装置装配图3. 对电弧炉废钢预热装置的主要零部件进行设计计算4. 进行输送装置装配图以及零件图的绘制以及计算5. 应力的分析 6. 电机的选型7. 带传动的设计计算8. 链传动的设计计算9. 输送装置轴承、齿轮、机架等的计算与选择10. 进行论文的撰写以及修改11. 完成外文文献的翻译二、存在问题及解决措施存在问题：1.将计算部分有些公式之类的存在问题2.装配图有瑕疵，达不到对废钢进行预热的效果3.三维建模一些细节问题解决措施：1. 仔细研读参考文献进行公式的甄别以及选择2. 将装配图进行优化，重新设计一些小部位3. 根据装配图零件进行三维建模三、后期工作安排第11-12周:撰写设计说明书初稿第13周:完成论文最后的修改完善，以及对装配图纸和零件图纸进行再次校核，计算部分的再次审核第14周:参加答辩，上交纸质版开题报告，任务书，毕业论文归档；电子版开题报告，任务书，毕业论文等材料归档。 指导教师签字： 年 月 日注：1. 正文：宋体小四号字，行距22磅；标题：加粗 宋体四号字2. 中期报告由各系集中归档保存，不装订入册。Discrete Optimization Modeling the reentrant job shop scheduling problem with setups for metaheuristic searches Jeriad Zoghby *, J. Wesley Barnes, John J. Hasenbein Graduate Program in Operations Research and Industrial Engineering, Department of Mechanical Engineering, The University of Texas at Austin, Austin, TX 78712, USA Received 10 December 2001; accepted 31 March 2004 Available online 8 June 2004 Abstract We consider modeling the reentrant job shop scheduling problem with sequence dependent setup times in the context of metaheuristic search methods. We begin by investigating feasibility conditions when sequence dependent setups are incorporated into the traditional job shop scheduling problem. The investigation reveals that traditional methods of avoiding infeasible solutions for iterative search techniques do not suffi ce. The conditions under which these infeasible solutions occur are presented and an algorithm is presented to remove such infeasibilities. Reentrancy and its rela- tionship to the traditional model are then illustrated, and the new features of the disjunctive graph are introduced. We conclude with a simple algorithm for obtaining an initial feasible solution, benefi ts of this research, and an application to the reentrant job shop scheduling problem with sequence dependent setups. ? 2004 Elsevier B.V. All rights reserved. Keywords: Metaheuristics; Scheduling; Flexible manufacturing systems; Manufacturing; Graph theory 1. The disjunctive graph model In this paper, we consider a variation of the classical job shop scheduling problem, the reentrant job shop scheduling problem with sequence depen- dent setups. This is an extension of the classical job shop scheduling problem, denoted Jmkc, which is introduced and defi ned in Section 2.1. The reen- trant job shop scheduling problem with sequence dependent setups, denoted Jmjsjk;recrcjc, extends the classical model by allowing for sequence dependent setup times between adjacent opera- tions on any machine and relaxing the restriction that each job visits a machine only once. The Jmkc is a well-known NP-hard problem 17, which has spurred an extensive and rapidly growing body of literature. Much of the recent research has revolved around dispatching rules, decomposition methods, and metaheuristic search techniques. Simple heuristic rules have dominated this area of research 27. Least slack policies and bottleneck starvation policies are scheduling techniques based *Corresponding author. Present address: 646 S. Main Ave., San Antonio, TX 78204, USA. Tel.: +1-210-938-7386; fax: +1- 210-938-3138. E-mail addresses: jeriad, jmzmail.utexas. edu (J. Zoghby), wbarnes (J. Wesley Barnes), jhas (J.J. Hasenbein). 0377-2217/$ - see front matter ? 2004 Elsevier B.V. All rights reserved. doi:10.1016/j.ejor.2004.03.027 European Journal of Operational Research 167 (2005) 336348 /locate/dsw on pulling WIP (work in progress). Least slack policies pull WIP to the end of the process line based on due dates or estimated cycle times 29,30. Bottleneck starvation policies pull WIP to the bottleneck based on Goldratts Theory of Constraints 19,20,28. There are also a consider- able number of other dispatching rules that have been developed across many industries 9,33. Decomposition methods attempt to develop solutions to complex problems by decomposing them into a number of smaller subproblems which are more tractable and easier to understand 32. The most successful of these methods, the Shifting Bottleneck approach 1,2,22, takes advantage of the disjunctive graph structure introduced by Roy and Sussman 34. By decomposing the problem into a series of single-machine subproblems, the technique iteratively schedules each machine while focusing on the bottleneck 35. Branch and bound methods have also incorporated a decomposition model 10, but generally perform very poorly on large problems due to the excessive computing time. Like decomposition methods, metaheuristics use the disjunctive graph model of the Jmkc. However, many metaheuristics rely heavily on guidance provided by Balas 3 to maintain feasi- bility during the search. For problems without sequence dependent setups, Balas showed that reversing arcs on the critical path maintains fea- sibility, and that such arc reversals are the only single reversals that could lead to improved solu- tions. Balas insights are the key to developing iterative methods, which can effi ciently search the complex solution space of the Jmkc. The last two decades have seen the growth of metaheuristic techniquessuccessfullyappliedtoproduction schedulingproblems57,12,13,18,25.Genetic algorithms, which do not necessarily use the dis- junctive graph, have been applied to these types of problems 8,11,21,24,31, but without considering the underlying structure or investigating the fea- sibility conditions of these models. Although there is substantial research with regard to Flow Shop Scheduling Problems with setups 15, they do not pose the same feasibility issues as Jmkc problems. The purpose of the paper is to present structural results and algorithms based on the disjunctive graph formulation of the Jmjsjk;recrcjc. Our belief is that investigation of this structure can lead to improved metaheuristic search methods for this problem, however we do not pursue an empirical investigation here. We present a disjunctive graph formulation of the problem and results related to the nature of feasible solutions represented in the graph. We also provide an ejection chain algo- rithm to return infeasible solutions to feasibility. We begin by extending the Jmkc to allow sequence dependent setups (Jmjsjkjc). We then further ex- tend this model to allow for reentrancy, where jobs are allowed to revisit machines (Jmjsjk;recrcjc). The purpose of presenting these extended models is to allow for metaheuristic techniques, such as Tabu Search, to perform effi cient searches of the feasible solution space. In Section 2, we begin with a brief recounting of the disjunctive graph formulation of the Jmkc 34 and the rule that guarantees feasibility while per- forming iterative moves toward the solution of the Jmkc 3. We then present a simple counterexample to the feasibility rule in a Jmjsjkjc disjunctive graph. The example illustrates that reversing a disjunctive arc on the critical (longest) path may not guarantee feasibility, i.e., a subsequent acyclic disjunctive graph, when one or more machine sequence dependent setups are present. These set- up-induced infeasibilities are then examined to determine the conditions under which they occur and an algorithm is presented which will remove any cycles that are formed. The Jmjsjkjc is then further extended to form the Jmjsjk;recrcjc, which allows for machines to be revisited, i.e., a job may possess two or more operations that require the same machine. The Jmjsjk;recrcjc and its rela- tionship to the Jmjsjkjc are then detailed. We conclude with an algorithm for fi nding an initial feasible solution for the Jmjsjk ;recrcjc, benefi ts of the research, and an industrial application. 2. The disjunctive graph model Much of the metaheuristic research on the Jmkc has relied upon the work of Roy and Sussman 34 and Balas 3. By modeling the problem as a dis- junctivegraph,RoyandSussmanpermitted J. Zoghby et al. / European Journal of Operational Research 167 (2005) 336348337 researcherstocaptureimportantscheduling information in a simple model. Balas extended their work by iteratively fi nding better solutions while maintaining feasibility from iteration to iteration. Balas work is the key to the success of many metaheuristic approaches, providing guid- ance on maintaining feasibility and avoiding non- improving moves. 2.1. The job shop scheduling problem The JmkCmaxconsists of a set # of n jobs, a set M of m machines, and a set O of N operations. Each operation v 2 O belongs to a job Jv2 # and is processed on a machine Mv2 M for a processing time of pv2 R . There is also a binary relation fi from O to O that defi nes the technological prece- dence of operations v;w belonging to the same job, Jv Jw. The problem of minimizing the makespan reduces to fi nding a release time rvfor each oper- ation v 2 O such that MiniMax v2O rv pv1 subject to rw? rvPpvif v ! w; v;w 2 O;2 rw? rvPpv_ rv? rwPpw if Mv Mw; v;w 2 O;3 rvP08v 2 O:4 In order to solve this problem via metaheuristic techniques it is advantageous to represent it as a disjunctive graph model. The disjunctive graph G V ;A;E consists of a set of nodes V , con- junctive arcs A, and disjunctive arcs E defi ned as follows: V O f0;N 1g, where 0 represents a source node, N 1 represents a sink node, both of which are virtual nodes not representing actual operations. A fv;wjv;w 2 O;v ! wg f0;wjw 2 O; 9 =v 2 O : v ! wg fv;N 1jv 2 O; 9 =w 2 O : v ! wg, where these arcs defi ne the technolog- ical precedence of operations within each job, and the relationships between jobs and the source and sink nodes. This set defi nes the con- junctive arcs, which have fi xed orientation and defi ne the technological precedence in the graph. The arc length defi nes the amount of time re- quired to process the operation at the tail of the arc. For arcs (0, w), the arc length can be used to represent the release delay for job Jw. E fv;wjMv Mw g, where these arcs defi ne the order of processing for operations on the same machine. These arcs represent the con- straint (3) above, and the orientations of these arcs defi ne the current solution of the graph. Fig. 1 presents an example of a disjunctive graph of a Jmkc with 3 machines, 3 jobs, and 3 operations per job. Node sets f1;2;3g, f4;5;6g, and f7;8;9g defi ne the operations for the 3 jobs, and node sets f1;5;9g, f2;4;8g, and f3;6;7g partition the operations among the 3 machines. The conjunctive arcs are denoted by solid lines and have a fi xed orientation, while disjunctive arcs are denoted by dashed lines and have no a priori fi xed orientation. Conjunctive arc lengths represent the time required before the job can begin a new operation. Disjunctive arc lengths represent the time required before the machine is free to begin processing the next operation. A selection of dis- junctive arc orientations represents a distinct ordering of operations on each machine. A new feasible solution can be found by reversing the orientation of a disjunctive arc on the critical (longest) path in the graph 3. Feasibility can be maintained by limiting the candidate arcs for reversal to disjunctive arcs on the critical path in the graph, given that the current solution is feasible. Balas proved that only arc reversals on the critical path could make iterative improvements in the makespan of the JmkCmax3. Fig. 1. The disjunctive graph of the Jmkc. 338J. Zoghby et al. / European Journal of Operational Research 167 (2005) 336348 By switching critical path disjunctive arcs, meta- heuristic search algorithms are able to effi ciently search the feasible solution space for improving solutions. 2.2. The job shop scheduling problem with setups Sequence independent setup delays are easily incorporated into the classical model and require no change in the iterative procedure. Such a delay is simply added to the duration of all arcs origi- nating at an operation node 3. A sequence dependent setup imposes an extra delay, in addi- tion to the current operation processing time, be- fore a particular machine can begin working on the next operation in its sequence. In the Jmjsjkjc, this sequence dependent setup time is added only to the unique associated disjunctive arc. Reversing an arc on the critical path does not always guarantee feasibility. The simple Jmjsjkjc model of Fig. 2 with 2 jobs, 4 operations, and 2 machines illustrates this fact. In Fig. 2, a single sequence dependent setup time of 12 units is present and takes place only when operation 3 precedes operation 2. Therefore, Arc 3;2 has a length of 17 while Arc 3;4 has a length of 5. This implies that the processing time for operation 3 is 5 time units, while the sequence dependent setup delay of operation 3 preceding operation 2 is 12 time units. The critical path of the graph is f0;3;3;2;2;5g, which has a length of 22. Arc 3;2 is the only disjunctive arc on the critical path in the current graph. However, its reversal creates the cycle f3;4;4;1;1;2;2;3g. Therefore the current graph cannot move to another feasible solution by only considering arcs on the longest path. An arc is a Cycle Generating Arc (CGA), when it is on the critical path and its reversal will create a cycle. An algorithm to remove cycles from the disjunctive graph is presented later. Sequence dependent setups are added only to the disjunctive arcs. If they are added to both the disjunctive and conjunctive arcs in the graph, this is equivalent to setups not beginning until both the job and machine are available. However, in a deterministic scheduling environment, the next operation is assumed to be known and delaying a setup until a job arrives would be ineffi cient if a machine is idle anyway. Although such setups could lead to an ineffi cient schedule, they would also avoid creating cycles in the graph, since the conjunctive and disjunctive arcs originating at a node would be of equal length. Our example shows that feasibility of the Jmjsjkjc is not guaranteed when reversing arcs on the critical path. This illustrates a concern when applying metaheuristic techniques to solve this problem. Critical path arcs are still the only arcs whose single reversal can improve the solution of the makespan 3. However, feasibility can no longer be guaranteed when searching the solution space by such reversals. The next section investi- gates the cycles created by single arc reversals and provides the necessary criteria for their existence. 3. Investigating cycles in the disjunctive graph A cycle composed only of disjunctive arcs im- plies the illogical condition in the schedule that an operation performed by a particular machine must precede itself. Our results below implicitly assume that these cycles can be avoided when moving between the solutions in a job shop problem. Cy- cles which are composed only of disjunctive arcs are referred to as DA (disjunctive arc) cycles. Any cycle not in the class of DA cycles is called a NDA cycle (non-disjunctive arc cycle). It can be shown that some classes of job shop problems cannot contain DA cycles. For example, White and Rogers37showthatifacertaintriangle inequality involving the sequence dependent setup times is satisfi ed for all triplets of operations, than a DA cycle is not possible in the disjunctive graph representation of the problem. Even if DA cyclesFig. 2. Infeasible example of the Jmjsjkjc. J. Zoghby et al. / European Journal of Operational Research 167 (2005) 336348339 are possible, they can be explicitly avoided in a software representation of the problem by model- ing machine cliques via arrays 1. Therefore, un- less stated otherwise, graphs considered in the rest of this paper are assumed not to contain DA cycles. To fully understand when solution infeasibili- ties occur, some basic propositions must be con- structed. All propositions in this section apply to the Jmkc, Jmjsjkjc, and Jmjsjk;recrcjc. Proposition 1. For any cycle to be created by reversing disjunctive Arc i;j, an alternate path must exist from nodes i to j. Proof. This was proven by Balas 3 for the Jmkc problem. The proofs for Jmjsjkjc and Jmjsjk;recrcjc are exactly analogous.h Proposition 2. Consider a solution which is feasible (i.e. does not contain any cycles) and a disjunctive arc v;w which is on the critical path. Suppose that reversal of arc v;w creates a NDA cycle and does not create any DA cycles. Then this NDA cycle contains a conjunctive arc originating from node v and a conjunctive arc terminating at node w. Proof. Consider a feasible solution in the disjunc- tive graph. Suppose disjunctive critical path arc (v;w) is such that its reversal to arc w;v creates an NDA cycle. In particular, there exists an alternate path from v to w. We show that the NDA cycle created must contain a conjunctive arc orig- inating from node v. We prove this by contradiction. So, suppose instead that all arcs originating from node v which are on the alternate path are disjunctive. Now consider a particular disjunctive arc on the alter- nate path v;u, where u is diff erent from w. Since disjunctive arcs v;w and v;u exist, this implies that operations (nodes) v;w;u are all assigned to the same machine. Therefore, there must exist a disjunctive arc connecting w and u. Furthermore, since node u is part of the alternate path from v to w, there is a path from u to w. Since the previous solution was feasible (before reversal of arc v;w), the disjunctive arc connecting nodes w and u must originate at nodeu as shown in Case II of Fig. 3. If not, then the previous solution was not feasible (as shown in Case I of Fig. 3). However, this implies that a DA cycle is created when arc v;w is re- versed. This contradicts our assumption that the reversal of v;w does not create any DA cycles. Hence, not all arcs on the alternate path which originate at node v can be disjunctive, i.e. there exists a conjunctive arc originating from node v in the cycle created by reversing arc v;w. Using a directly analogous argument, it can be shown that under the assumptions of the theorem a conjunctive arc terminates at node w.h Proposition 2 implies that a NDA cycle must contain at least two conjunctive arcs and one dis- junctive arc (the arc being reversed). Proposition 3 shows that a NDA cycle must contain at least one other disjunctive arc. Proposition 3. All NDA cycles requ
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号