第1页 / 共93页
第2页 / 共93页
第3页 / 共93页
第4页 / 共93页
第5页 / 共93页
第6页 / 共93页
第7页 / 共93页
第8页 / 共93页
动态规划原版论文.pdf
Static and dynamic job-shop scheduling using rolling-
horizon approaches and the Shifting Bottleneck Procedure
By
Ahmed S. Ghoniem
Thesis submitted to the faculty of the
Virginia Polytechnic Institute and State University
In partial fulfillment of the requirements for the degree of
Master of Science
In
Joint graduate program with
Ecole des Mines de Nantes - France
Industrial and Systems Engineering
within the
Dr. Subhash C. Sarin, Chairman – co-advisor
Dr. Stéphane Dauzère-Pérès, Co-advisor EMNantes
Dr. Hanif D. Sherali, Committee Member
Dr. Robert C. Williges, Program Chairman
September 2002
Nantes, France
Keywords: job-shop scheduling, rolling horizon approach, decomposition
methods, shifting bottleneck procedure, static/dynamic scheduling.
© 2002, Ahmed Ghoniem
Static and dynamic job-shop scheduling using rolling-horizon approaches
and the Shifting Bottleneck Procedure
by Ahmed Ghoniem
Abstract
Over the last decade, the semiconductor industry has witnessed a steady increase in its
complexity based on improvements in manufacturing processes and equipment. Progress in
the technology used is no longer the key to success, however. In fact, the semiconductor
technology has reached such a high level of complexity that improvements appear at a slow
pace. Moreover, the diffusion of technology among competitors shows that traditional
approaches based on technological advances and innovations are not sufficient to remain
competitive.
A recent crisis in the semiconductor field in the summer 2001 made it even clearer
that optimizing the operational control of semiconductor wafer fabrication facilities is a vital
key to success. Operating research-oriented studies have been carried out to this end for the
last 5 years. None of them, however, suggest a comprehensive model and solution to the
operational control problem of a semiconductor manufacturing facility.
Two main approaches, namely mathematical programming and dispatching rules, have
been explored in the literature so far, either partially or entirely dealing with this problem.
Adapting the Shifting Bottleneck (SB) procedure is a third approach that has motivated many
studies.
Most research focuses on optimizing a certain objective function under idealized
conditions and thus does not take into consideration system disruptions such as machine
breakdown. While many papers address the adaptations of the SB procedure, the problem of
re-scheduling jobs dynamically to take disruptions and local disturbances (machines
breakdown, maintenance...) into consideration shows interesting perspectives for research.
Dealing with local disturbances in a production environment and analyzing their impact on
scheduling policies is a complex issue. It becomes even more complex in the semiconductor
industry because of the numerous inherent constraints to take into account. The problem that
is addressed in this thesis consists of studying dynamic scheduling in a job-shop environment
where local disturbances occur. This research focuses on scheduling a large job shop and
developing re-scheduling policies when local disturbances occur. The re-scheduling can be
applied to the whole production horizon considered in the instance, or applied to a restricted
period T that becomes a decision variable of the problem. The length of the restricted horizon
T of re-scheduling can influence significantly the overall results. Its impact on the general
performance is studied. Future extensions can be made to include constraints that arise in the
semiconductors industry, such as the presence of parallel and batching machines, reentrant
flows and the lot dedication problem.
The theoretical results developed through this research will be applied to data sets to study
their efficiency. We hope this methodology will bring useful insights to dealing effectively
with local disturbances in production environments.
Dedication
I would like to dedicate this thesis to my parents.
iv
Acknowledgments
In the first place, I would like to express my gratitude towards Dr. Stéphane Dauzère-Pérès
and Dr. Subhash Sarin for giving me the opportunity of working under their guidance. Their
support and trust helped me in developing my own ideas and implementing them successfully.
Dr. Stéphane Dauzère-Pérès helped me in carrying out my research for the Master’s Thesis
under ideal conditions in the Department of Automatic Control and Industrial Engineering at
the Ecole des Mines de Nantes (France).
I would like to thank heartily Dr. Hanif Sherali who kindly accepted to serve in my
committee. I appreciate much the support he gave me during my stay in Blacksburg (Spring
2001) and after I came back to France.
From February 2002 to September 2002, Fabrice Delmotte was my office mate in the
Department of Automatic Control and Industrial Engineering at the Ecole des Mines de
Nantes (France). I appreciated sharing the office with him and the friendly discussions we had
together.
In addition, I would like to thank all the professors who contributed to the creation of this dual
MS degree between Virginia Tech and the Ecole des Mines de Nantes. I am glad to be a
pioneer of this promising program.
Finally, all my gratitude goes to my parents for what they did and do for our family and me.
v
Table of Contents
ABSTRACT ............................................................................................................................. B
DEDICATION........................................................................................................................IV
ACKNOWLEDGMENTS ...................................................................................................... V
1. BACKGROUND................................................................................................................... 1
A. INTRODUCTION TO THE PROBLEM....................................................................................... 1
1. The Semiconductor Industry....................................................................................... 1
2.
Specific constraints .................................................................................................... 2
3. Dynamic behaviour .................................................................................................... 3
B. PROBLEM DEFINITION ..................................................................................................... 4
1. Preliminary note......................................................................................................... 5
2. Phase 1: Scheduling phase......................................................................................... 6
3. Phase 2: Rescheduling phase..................................................................................... 8
C. RESEARCH GOALS ............................................................................................................ 12
1. Research Questions.................................................................................................. 12
2. Problem Hypotheses................................................................................................. 12
3. Research Objectives ................................................................................................. 13
4. Significance of Proposed Research.......................................................................... 13
2. LITERATURE REVIEW.................................................................................................. 15
A. SEMICONDUCTOR MANUFACTURING ................................................................................ 15
B. SHIFTING BOTTLENECK PROCEDURE ................................................................................ 15
C. REACTIVE SCHEDULING.................................................................................................... 16
3. METHODOLOGY............................................................................................................. 23
A. DISJUNCTIVE GRAPH...................................................................................................... 23
B. THE SHIFTING BOTTLENECK PROCEDURE ..................................................................... 24
C. THE ROLLING HORIZON APPROACH................................................................................ 26
1. Overview.................................................................................................................... 26
2. Optimization of each time window............................................................................ 27
3. Assignment of operations to time windows ............................................................... 27
D. PROPOSED APPROACH AND METHODOLOGY .................................................................... 28
4. RESULTS............................................................................................................................ 29
A. PHASE 1: SCHEDULING WITH R.H. HEURISTICS ................................................................ 29
1. The General Scheme................................................................................................. 29
2. An example ............................................................................................................... 30
3. Number of time-windows.......................................................................................... 35
4. Improved Decomposition Heuristic (IDH)............................................................... 41
5. Some Results............................................................................................................. 43
B. PHASE 2: RE-SCHEDULING PHASE .................................................................................... 46
1.
Introduction.............................................................................................................. 46
2. Notations and hypothesis ......................................................................................... 47
3. General Scheme........................................................................................................ 48
4. An example ............................................................................................................... 50
5. Length of R.H. ........................................................................................................... 54
CONCLUSION....................................................................................................................... 58
vi
APPENDIX: ELEMENTS OF CODE IMPLEMENTED IN JAVA LANGUAGE......... 59
BIBLIOGRAPHY .................................................................................................................. 81
VITA........................................................................................................................................ 85
vii
Table of Figures
Figure 1 - A Disjunctive Graph.................................................................................................. 6
Figure 2 - Disjunctive graph with time windows....................................................................... 7
Figure 3 - Disjunctive Graph with time windows in the event of a system disruption.............. 9
Figure 4 - Disjunctive Graph and the re-scheduling phase ...................................................... 11
Figure 5 - A Disjunctive Graph................................................................................................ 24
Figure 6 - Rolling Horizon Heuristic on a single machine ...................................................... 26
Figure 7 – Decomposition Heuristic general scheme............................................................... 30
Figure 8 - Overall graph for a 4x4 instance ............................................................................. 31
Figure 9 - Graph corresponding to the 1st time-window ......................................................... 31
Figure 10 - Gantt Diagram for the first time window of the problem...................................... 32
Figure 11 - Graph associated to the second time window........................................................ 33
Figure 12 - Gantt diagram showing an overlapping................................................................. 33
Figure 13 - Gantt Diagram for the Decomposition Heuristic................................................... 34
Figure 14 - Impact of the number of subwindows; 5x10 and 5x15 problems ......................... 35
Figure 15 - Impact of the number of subwindows; 5x20 problems ......................................... 36
Figure 16 - Impact of the number of subwindows; 10x10 problems ....................................... 36
Figure 17 - la-09 instance......................................................................................................... 37
Figure 18 - la-15 instance......................................................................................................... 37
Figure 19 - CPU time for DH for 5x10 instances, according to the number of subwindows .. 38
Figure 20 - CPU time for DH for 5x15 instances, according to the number of subwindows .. 39
Figure 21 - CPU time for DH for 5x20 instances, according to the number of subwindows .. 40
Figure 22 - Construction of the solution with the IDH ............................................................ 42
Figure 23 - Updating the nodes in the second time window.................................................... 42
Figure 24 - Comparison between three heuristics for 5x10 problems ..................................... 43
Figure 25 - Comparison between three heuristics for 5x15 problems ..................................... 44
Figure 26 - Comparison between three heuristics for 5x20 problems ..................................... 44
Figure 27 - Comparison between three heuristics for 10x10 problems ................................... 45
Figure 28 - CPU time for 5x10, 5x15 and 5x20 problems....................................................... 45
Figure 29 - Gantt Diagram before re-scheduling ..................................................................... 47
Figure 30 - Re-Scheduling general scheme.............................................................................. 48
Figure 31 - Scheduled Graph with a SB procedure.................................................................. 50
Figure 32 - Gantt Diagram for a 4x4 instance.......................................................................... 50
Figure 33 - Reconstruction of the schedule to deal with a breakdown .................................... 51
Figure 34 - Reconstruction of the graph to deal with a breakdown ......................................... 51
Figure 35 - Cmax for (L,m) = (50,4)........................................................................................ 52
Figure 36 - Cmax for (L,m) = (50,3)........................................................................................ 53
Figure 37 - Cmax for R.H. shrinking, la-02 instance............................................................... 54
Figure 38 - CPU time in ms for R.H. shrinking, la-02 instance............................................... 55
Figure 39 – Cmax for R.H. shrinking; la06 instance, (t,m, L) = (60, 3, 300). ........................ 56
Figure 40 – CPU time for R.H. shrinking; la06 instance, (t,m,L) = (60,3,300)....................... 56
viii
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
