Applied Cluster Computing for NP - Hard Problem

การประยุกต์ใช้เทคโนโลยีคลัสเตอร์เพื่อแก้ปัญหา NP-Hard

Applied Cluster Computing for NP-Hard problem

บทสรุปสำหรับผู้บริหาร (Executive Summary)

          งานวิจัยนี้มีวัตถุประสงค์เพื่อนำความรู้เกี่ยวกับการนำระบบคอมพิวเตอร์คลัสเตอร์มาประยุกต์ใช้ในการแก้ปัญหาการตัดสินใจที่มีขนาดใหญ่และซับซ้อน (Large-scale and complex decision problem) หรือเรียกว่า ปัญหา NP-Hard ปัญหา NP-Hard เกิดขึ้นในทุกๆภาคธุรกิจและอุตสาหกรรม อาทิเช่น ปัญหาการจัดเส้นทางของยานพาหนะ (Vehicle routing problem) ปัญหาการจัดตารางเวลาการผลิต (Job scheduling problem) ปัญหาการเปรียบเทียบยีนหรือโครโมโซมในวงการแพทย์ (DNA matching) และปัญหาการจัดการความล่าช้าในเครือข่ายสื่อสาร (Communication network problem) เป็นต้น ปัญหาในภาคธุรกิจและอุตสาหกรรมเหล่านี้เป็นปัญหาที่มีตัวแปรการตัดสินใจจำนวนมาก และตัวแปรมีความสัมพันธ์กันอย่างซับซ้อน ซึ่งยากยิ่งต่อการหาคำตอบที่ดีที่สุด (Optimal solution) ในโครงงานวิจัยนี้ ได้ออกแบบและพัฒนาระบบคอมพิวเตอร์คลัสเตอร์เพื่อนำมาใช้ในองค์กรภาคธุรกิจและอุตสาหกรรม หรือแม้แต่ระบบภายในมหาวิทยาลัยที่ไม่มีการใช้งานทรัพยากรคอมพิวเตอร์หรือใช้งานไม่เต็มที่ เพื่อใช้ในการหาคำตอบของปัญหา NP-Hard ซึ่งจะส่งผลให้ลดการสิ้นเปลืองพลังงานและทรัพยากรขององค์กร และประเทศได้อย่างมาก

1. ความเป็นมาและความสำคัญของเรื่อง

           ในปัจจุบันนี้ยังมีปัญหาการตัดสินใจ (Decision problem) จำนวนมากที่ไม่สามารถหาคำตอบได้โดยการใช้คอมพิวเตอร์เพียงเครื่องเดียว เพราะว่าใช้เวลาในการหาคำตอบนานเกินไป ซึ่งอาจต้องใช้เวลาในการคำนวณนานหลายๆชั่วโมง หลายวัน หรือหลายปี จนกว่าที่เครื่องคอมพิวเตอร์จะสามารถหาคำตอบที่ดีที่สุด (Optimal solution) ของปัญหาการตัดสินใจนั้นๆได้ โดยเฉพาะอย่างยิ่งปัญหา NP-Complete หรือ NP-Hard ซึ่งที่มีความซับซ้อนมาก และ ยากต่อการหาคำตอบที่ดีที่สุด ( ณกร , 2548) เมื่อเราลองพิจารณาดูว่า หากใช้คอมพิวเตอร์เพียงเครื่องเดียวมาแก้ปัญหา NP-Hard นี้ อาจจะต้องใช้เวลาในการคำนวณเป็นพันๆปีหรืออาจจะนานเป็นปีแสงเลยก็เป็นได้ ตารางที่ 1 แสดงตัวอย่างของเวลาที่เครื่องคอมพิวเตอร์ใช้ในการหาคำตอบที่ดีที่สุดของปัญหาการเลือกเส้นทางของบุรุษไปรษณีย์ (Traveling postman/sale man problem : TSP)

ตารางที่ 1 ความสัมพันธ์ระหว่างจำนวน Node และเวลาที่ใช้ในการหาคำตอบ

จำนวน Node

เวลาที่ใช้ ( นาที )

5

0.0000

6

0.0000

7

0.0003

8

0.0005

9

0.0057

10

0.0686

11

0.8879

12

1.7758

13

23.0854

14

323.1956

          จากตารางจะเห็นได้ว่าเมื่อจำนวนเมือง (Node) ที่บุรุษไปรษณีย์จะต้องนำจดหมายไปส่งมีจำนวนมากขึ้น เวลาที่ใช้ในการหาคำตอบที่ดีที่สุด ( เส้นทางในการเดินทางที่สั้นที่สุด) จะเพิ่มขึ้นแบบแฟคทอเรียล (Factorial) เมื่อจำนวน Node เท่ากับ 14 Node จะใช้เวลาในการเส้นทางที่สั้นที่สุดเท่ากับ 323.20 นาที หรือเท่ากับ 5.39 ชั่วโมงเลยทีเดียว
          อย่างไรก็ตาม ปัญหาการตัดสินใจเหล่าต่างๆนี้สามารถหาคำตอบได้ภายในระยะเวลาที่เร็วมากขึ้น เมื่อนำเอาใช้เทคโนโลยีคอมพิวเตอร์คลัสเตอร์ (Cluster computing) เข้ามาประยุกต์ใช้ คอมพิวเตอร์ คลัสเตอร์เป็นเทคโนโลยีที่นำเอาคอมพิวเตอร์ธรรมดาๆ (Standard PC) หลายๆตัวมาเชื่อมต่อกันแบบขนานเพื่อร่วมกันทำการประมวลผล ซึ่งมีประสิทธิภาพเทียบเท่ากับเครื่อง Super Computer เครื่องหนึ่งเลยทีเดียว ระบบคอมพิวเตอร์คลัสเตอร์นี้สามารถติดต่อและทำงานร่วมกันและกันโดยใช้อัลกอริทึมที่พัฒนาโดยภาษาคอมพิวเตอร์ต่างๆเช่น Java RMI ซึ่งเป็นภาษาที่มีประสิทธิภาพสูง
          อีกหนึ่งปัญหาที่พบได้บ่อยในองค์กรภาคธุรกิจและอุตสาหกรรมส่วนใหญ่ ก็คือปัญหาการใช้งานคอมพิวเตอร์ในสำนักงานอย่างไม่คุ้มค่า ไม่เต็มประสิทธิภาพ บางเครื่องถูกเปิดทิ้งไว้โดยไม่มีการใช้งาน หรือใช้งานง่ายๆ ไม่หนักมากนัก เช่น ฟังเพลง พิมพ์งาน ทำให้สิ้นเปลืองทรัพยากร และพลังงานเป็นอันมาก ผู้วิจัยจึงเล็งเห็นช่องทางในการแก้ปัญหานี้โดยใช้วิธีการ “ แชร์คอมพิวเตอร์ ” ในบริษัทเข้าด้วยกัน ด้วยการประยุกต์ใช้เทคโนโลยีคอมพิวเตอร์คลัสเตอร์ ติดต่อกันด้วยภาษา Java RMI และระบบจะมีการจัดการฐานข้อมูลโดยใช้ my SQL หากคอมพิวเตอร์ในสำนักงานเครื่องใดไม่มีการใช้งาน หรือใช้งาน CPU ไม่เต็มประสิทธิภาพ ก็สามารถนำมาใช้ร่วมกันในการคำนวณหาคำตอบของปัญหา NP-Hard หรือปัญหาการตัดสินใจอื่นๆที่ต้องการได้ และเมื่อมีผู้ที่ต้องการใช้งานคอมพิวเตอร์เครื่องนั้นๆก็สามารถใช้งานได้ทันที โดยที่เครื่องจะหยุดการคำนวณไว้แล้วหันไปทำงานที่ผู้ใช้สั่งได้เลย ด้วยการประยุกต์ใช้งานเทคโนโลยีคอมพิวเตอร์คลัสเตอร์ดังกล่าวนี้จะส่งผลให้องค์กรภาคธุรกิจและอุตสาหกรรมสามารถประหยัดงบประมาณ ลดค่าใช้จ่ายลงไปได้มากมาย รวมทั้งทำให้เกิดการใช้ประโยชน์จากทรัพยากรคอมพิวเตอร์ของบริษัทได้อย่างมีประสิทธิภาพมากยิ่งขึ้น

2. วัตถุประสงค์
          1. เพื่อสามารถออกแบบและพัฒนาเทคโนโลยีคอมพิวเตอร์คลัสเตอร์ให้กับองค์กรภาคธุรกิจและอุตสาหกรรม
          2. เพื่อสามารถนำวิธีเทคโนโลยีคอมพิวเตอร์คลัสเตอร์ที่ได้ออกแบบและพัฒนาขึ้นไปใช้แก้ปัญหาการตัดสินใจที่มีขนาดใหญ่และซับซ้อน

3. ขอบเขตการศึกษา
          1. ออกแบบและพัฒนาระบบคอมพิวเตอร์คลัสเตอร์โดยใช้เครื่องคอมพิวเตอร์ที่มีอยู่แล้วในองค์กร
          2 . ศึกษาการทำงานและพัฒนาประสิทธิภาพของภาษา Java RMI ซึ่งที่ใช้ติดต่อกันในระบบระบบคอมพิวเตอร์คลัสเตอร์ที่สร้างขึ้นมา
          3. สร้างระบบคอมพิวเตอร์คลัสเตอร์ที่นำมาแก้ปัญหา NP-Hard ได้
          4. ออกแบบและพัฒนาระบบการแชร์คอมพิวเตอร์ในองค์กรที่ไม่มีการใช้งาน หรือใช้งานไม่เต็มประสิทธิภาพ มาร่วมกันแก้ปัญหา NP-Hard
          5 . ออกแบบและพัฒนาโปรแกรม mySQL เพื่อใช้ในการดูแลและจัดการระบบฐานข้อมูลที่ นำมาใช้ในการคำนวณเพื่อแก้ปัญหาการตัดสินใจในองค์กรภาคธุรกิจ และอุตสาหกรรม
          6. แสดงตัวอย่างการประยุกต์ใช้ระบบคอมพิวเตอร์คลัสเตอร์ในการแก้ปัญหาการจัดตารางเวลาและเส้นทางของรถบรรทุก ของบริษัทกรณีศึกษา

4. แผนการทำงาน
วิธีดำเนินการศึกษาประกอบด้วยขั้นตอนดังนี้

          1. ศึกษาการทำงานของระบบคอมพิวเตอร์คลัสเตอร์
          2. ศึกษาเทคโนโลยี Java RMI ที่จะนำมาใช้ติดต่อกันในระบบคลัสเตอร์
          3. ศึกษาและออกแบบวิธีการสร้างและจัดการเครื่องคอมพิวเตอร์แม่ข่าย ( Server) และเครื่องคอมพิวเตอร์ลูกข่าย (Client)
          4. ศึกษาและออกแบบการแจกจ่ายงานระหว่างเครื่อง Client กับเครื่อง Server ที่ทำงานอยู่ในระบบคลัสเตอร์
          5. ศึกษาและออกแบบวิธีการสร้างระบบ Cluster ที่ทำหน้าที่แก้ปัญหา NP-Hard
          6. ศึกษาและออกแบบการทำงานของโปรแกรมจัดการฐานข้อมูล my SQL
          7. ศึกษาและออกแบบวิธีการแชร์ ( Share) คอมพิวเตอร์ในองค์กรที่ไม่มีการใช้งานหรือใช้งานไม่เต็มประสิทธิภาพ มาร่วมกันคำนวณปัญหา NP-Hard รวมทั้ง
          8. การประยุกต์ใช้ระบบคอมพิวเตอร์คลัสเตอร์ที่ได้พัฒนาขึ้นมาใช้ในการแก้ปัญหาการจัดตารางเวลาและเส้นทางของรถบรรทุกของบริษัทกรณีศึกษา

5. ผลที่คาดว่าจะได้รับ
          1. สามารถนำทรัพยากรคอมพิวเตอร์ที่มีอยู่ในองค์กรภาคธุรกิจและอุตสาหกรรมมาใช้ให้มีประสิทธิภาพมากยิ่งขึ้น
          2. สามารถนำระบบคอมพิวเตอร์คลัสเตอร์มาประยุกต์ใช้ในการแก้ปัญหาการตัดสินใจที่มีขนาดใหญ่และซับซ้อน ซึ่งสามารถช่วยให้บริษัทกรณีศึกษาลดค่าใช้จ่ายในการดำเนินการ
          3 . สามารถใช้เป็นแหล่งข้อมูลอ้างอิงในการค้นคว้าวิจัยต่อไป  

 

เอกสารอ้างอิง

Andrew S. Tanenbaum, Maarten Van Steen. Distributed systems: principles and Paradigms.Upper Saddle River , N.J. :        Prentice Hall, 2002.
Clifford J. Berg. Advanced Java 2development for enterprise applications. Mountain View, Calif. : 
       Sun Microsystems Press, 2000.
ณกร อินทร์พยุง. การแก้ปัญหาการตัดสินในในอุตสาหกรรมการขนส่งและลอจิสติกส์.กรุงเทพฯ : ซีเอ็ดยูเคชั่น, 2548.
มณีโชติ สมานไทย. คู่มือการออกแบบฐานข้อมูลและภาษา SQL ฉบับผู้เริ่มต้น. นนทบุรี :อินโฟเพรส, 2546
การสร้างซุปเปอร์คอมพิวเตอร์ราคาถูก ด้วยเทคโนโลยีพีซี คลัสเตอร์ . [ ออนไลน์ ]. เข้าถึงได้จาก :
       http://hpcnc.cpe.ku.ac.th/static/article/clusterall.pdf (วันที่ค้นข้อมูล : 9 เมษายนพ.ศ.2549)

<< Back