A scheduling in flexible flow shop problem with unrelated parallel machines and sequence-dependent setup times
Thesis (D.Eng.)--Chulalongkorn University, 2007
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | Book |
| Published: |
Chulalongkorn University,
2010-03-29T04:45:19Z.
|
| Subjects: | |
| Online Access: | http://cuir.car.chula.ac.th/handle/123456789/12363 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Thesis (D.Eng.)--Chulalongkorn University, 2007 To study a scheduling problem of flexible flow shop, where at least one production stage is made up of unrelated parallel machines, and setup times are sequence- and machine-dependent. The objective is to find a schedule that minimizes the makespan and the number of tardy jobs in a static scheduling environment. For this problem, a 0-1 mixed integer programming is formulated. The model is, however, a combinatorial optimization problem which is too difficult to be solved for large-sized problems, and hence, a heuristic is developed to obtain good solutions in reasonable time. The heuristic has three phases. The first phase uses a constructive algorithm. It starts with the generation of the operating time representative for each operation. Then, it uses a dispatching rule or a simple flow shop makespan heuristic to determine an initial solution. The improvement algorithm based on shift moves or pairwise interchanges of jobs is applied to improve the solution in the second phase. After that, a metaheuristic is used to refine the solution in the final phase. Several well-known heuristics are tested in each phase. The performances of the heuristics are compared to one another based on a set of test problems with up to 50 jobs and 20 stages and with an optimal solution for small-sized problems. The computational results indicate that the Nawaz, Enscore, and Ham (NEH) algorithm is most suitable for determining the initial solution, the all-pairwise-interchange approach is good for improving the solution, and the simulated annealing algorithm is best metaheuristic for refining the solution. ศึกษาปัญหาการจัดตารางการผลิตแบบไหลเลื่อนยืดหยุ่น (flexible flow shop) โดยมีขั้นตอนการผลิตอย่างน้อยหนึ่งขั้นตอนที่ใช้เครื่องจักรขนานกันที่ไม่สัมพันธ์กัน เวลาที่ใช้เพื่อการปรับตั้งเครื่องจักรจะขึ้นกับลำดับงานก่อนหน้าและเครื่องจักร โดยมีวัตถุประสงค์เพื่อจัดตารางการผลิตที่ทำให้เวลาปิดงานของระบบและจำนวนงานล่าช้ามีค่าน้อยที่สุด ภายใต้ภาวะของการจัดตารางการผลิตแบบสถิต (static) งานวิจัยนี้ได้สร้างโปรแกรมเชิงเส้นจำนวนเต็มแบบผสมและแบบทวิภาคสำหรับการแก้ปัญหา แต่ด้วยปัญหานี้ถือเป็นปัญหาการหาคำตอบที่ดีที่สุดเชิงการจัด (combinatorial optimization problem) ที่ยากเกินไปที่จะใช้แก้ปัญหาที่มีขนาดใหญ่ได้ ดังนั้นจึงได้พัฒนาฮิวริสติก เพื่อหาคำตอบที่ดีโดยใช้เวลาที่สมเหตุสมผล โดยฮิวริสติกนี้มีทั้งหมด 3 ขั้นในการหาคำตอบ ขั้นที่หนึ่งใช้วิธีสร้างเสริม (constructive algorithm) โดยเริ่มต้นจากการสร้างตัวแทนเวลาของแต่ละกระบวนการ แล้วนำแนวคิดของกฎการจ่ายงาน (dispatching rules) หรือฮิวริสติกสำหรับระบบการผลิตแบบไหลเลื่อนสามัญ (simple flow shop heuristics) มาใช้เพื่อสร้างคำตอบเบื้องต้น ขั้นที่สองใช้วิธีการเลื่อนงานหรือการสับเปลี่ยนงานมาปรับปรุงคำตอบ จากนั้นเป็นการนำวิธีเมต้าฮิวริสติกมาใช้เพื่อปรับปรุงคำตอบอีกครั้งในขั้นสุดท้าย ได้มีการทดสอบสมรรถนะของฮิวริสติกที่ใช้ในแต่ละขั้น ด้วยการเปรียบเทียบกับคำตอบที่ดีที่สุดจากกลุ่มปัญหาทดสอบที่มีจำนวนงานมากสุด 50 งาน และ ขั้นตอนมากสุด 20 ขั้นตอน ผลการทดลองชี้ให้เห็นว่าวิธีของ Nawaz Enscore และ Ham ที่เรียกว่าวิธี NEH เป็นวิธีที่เหมาะสมที่สุดในการหาคำตอบเริ่มต้น และวิธีการสับเปลี่ยนงานแบบ all-pairwise-interchanges เป็นวิธีการที่ดีสำหรับปรับปรุงคำตอบ และวิธี simulated annealing เป็นวิธีเมต้าฮิวริสติกที่ดีที่สุดสำหรับการปรับปรุงคำตอบให้ดีขึ้นอีก |
|---|---|
| Item Description: | http://cuir.car.chula.ac.th/handle/123456789/12363 |