Chulalongkorn University Theses and Dissertations (Chula ETD)

MULTI-PERIOD MULTI-SITE ASSIGNMENT PROBLEM WITH JOINT REQUIREMENT OF MULTIPLE RESOURCE TYPES

Other Title (Parallel Title in Other Language of ETD)

ปัญหาการมอบหมายงานที่มีหลายสถานีงานหลายช่วงเวลาโดยมีความต้องการใช้ทรัพยากรหลายประเภทร่วมกัน

Year (A.D.)

2013

Document Type

Thesis

First Advisor

Paveena Chaovalitwongse

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

Doctor of Philosophy

Degree Level

Doctoral Degree

Degree Discipline

Industrial Engineering

DOI

10.58837/CHULA.THE.2013.1377

Abstract

An assignment problem has been extensively studied and applied in many industries. This research proposes a multi-period multi-site assignment problem with joint requirement of multiple resource types. In this problem, there are many multi-skill resource types, and each task requires joint of more than one resource type to operate. The decisions in the proposed model are not only assigning resources to tasks as in classic assignment problems but also allocating resources to sites in each period. An integer linear programming model and a heuristic approach based on Tabu search algorithm (Two–step Tabu search heuristic) are developed. The specified neighborhood strategy, short-term memory and long-term memory are designed for the addressed problem in order to generate an efficient move to improve solutions. In addition, the surrogate objective is introduced to evaluate the quality of neighborhoods, and only good neighborhoods are considered to increase search speed. The quality of solutions from the developed heuristic are compared with optimal solutions from CPLEX. For small size problems, the result shows that the proposed heuristic can find solutions close to optimum in most problems at the average optimal gap of 0.09%. For medium size problems, the algorithm can provide good solutions in a reasonable time at the average optimal gap of 4.42%. Finally, for large size problems whose computational time of CPLEX is limited to 10 hours, the average gap between solutions from heuristic and upper bounds from CPLEX is 8.28%.

Other Abstract (Other language abstract of ETD)

ปัญหาการมอบหมายงานเป็นปัญหาที่มีการศึกษาและนำไปประยุกต์ใช้ในหลายอุตสาหกรรม วิทยานิพนธ์ฉบับนี้นำเสนอปัญหาการมอบหมายงานที่มีหลายช่วงเวลาหลายสถานีงาน โดยแต่ละงานต้องการใช้ทรัพยากรหลายประเภทร่วมกัน ในปัญหานี้ ทรัพยากรมีหลายประเภททักษะและงานต้องการใช้ทรัพยากรมากกว่าหนึ่งประเภทในการทำงาน การตัดสินใจในปัญหาดังกล่าว นอกจากจะต้องมอบหมายทรัพยากรให้ไปทำงานเหมือนปัญหาการมอบหมายงานทั่วไปแล้ว ยังต้องจัดสรรทรัพยากรให้ไปทำงานตามสถานีงานต่างๆในแต่ละช่วงเวลาอีกด้วย วิทยานิพนธ์ฉบับนี้ได้พัฒนาตัวแบบกำหนดการเชิงเส้นจำนวนเต็มและฮิวริสติกที่อาศัยหลักการของอัลกอลิทึมการค้นหาแบบทาบู (Two-step Tabu search heuristic) โดยที่กลยุทธ์การค้นหาคำตอบข้างเคียง (Neighborhood strategy) หน่วยความจำระยะสั้น (short-term memory) และหน่วยความจำระยะยาว (long-term memory) ได้ถูกออกแบบมาให้เหมาะสมกับปัญหาดังกล่าว นอกจากนี้ได้นำวัตถุประสงค์ทดแทน (Surrogate objective) มาใช้ประเมินคุณภาพของคำตอบข้างเคียงด้วย ในการเพิ่มความเร็วของการค้นหาคำตอบจะพิจารณาเฉพาะคำตอบข้างเคียงที่ดีเท่านั้น คุณภาพคำตอบจากฮิวริสติกที่พัฒนาขึ้นถูกประเมินโดยการนำไปเปรียบเทียบกับคำตอบที่ดีที่สุด (Optimum solution) ที่ได้จาก CPLEX โดยที่ผลการทดลองแสดงให้เห็นว่า สำหรับปัญหาขนาดเล็ก ฮิวริสติกที่นำเสนอสามารถหาคำตอบที่ใกล้เคียงกับคำตอบที่ดีที่สุดได้ โดยมีค่าเฉลี่ยช่วงห่างระหว่างคำตอบที่ได้จากฮิวริสติกและ CPLEX (Optimum gap) เท่ากับ 0.09% สำหรับปัญหาขนาดกลาง อัลกอริทึมสามารถหาคำตอบที่ดีได้ภายในเวลาที่เหมาะสม โดยมีค่าเฉลี่ยช่วงห่างระหว่างคำตอบเท่ากับ 4.42% และสำหรับปัญหาขนาดใหญ่ที่จำกัดเวลาการหาคำตอบของ CPLEX ไว้ที่ 10 ชั่วโมง ค่าเฉลี่ยช่วงห่างระหว่างคำตอบที่ได้จากฮิวริสติกและค่ามากสุดที่เป็นไปได้ของคำตอบ (Upper bound) จาก CPLEX เท่ากับ 8.28%

Link to Full Text

Share

COinS