เอกสารประชุมวิชาการระดับขาติมหาวิทยาลัยทักษิณ ครั้งที่ 28 2561

1177 งานวิจัยและนวัตกรรมเพื่อสังคมที่มั่นคง มั่งคั่ง และยั่งยืน (Research and Innovation for Social Stability, Prosperity and Sustainability) ปรับค่าใช้จ่ายในตารางปัญหาการมอบหมายงานดังนี้ ถ้า  B C เพิ่มค่าของสมาชิกทุกสมาชิกในแถวที่มีค่าใช้จ่ายรวมต่าสุดโดย    1 ij ij c c n ถ้า  B C ลดค่าของสมาชิกทุกสมาชิกในแถวที่มีค่าใช้จ่ายรวมสูงสุดโดย    1 ij ij c c n ขั้นตอนที่ ปรับค่าใช้จ่ายในตารางปัญหาการมอบหมายงานโดย          ˜ 1 2 1 1 ij ij i j c c B C โดยที่   1 i B คือค่าใช้จ่ายต่าสุดของแถวที่ i จากขั้นตอนที่ 1   1 i C คือค่าใช้จ่ายต่าสุดของหลักที่ j จากขั้นตอนที่ 1 ขั้นตอนที่ ปรับค่าใช้จ่ายในตารางปัญหาการมอบหมายงานโดย        2 3 2 ij ij i c c B โดยที่   2 i B คือค่าใช้จ่ายต่าสุดของแถวที่ i จากขั้นตอนที่ 2 ขั้นตอนที่ ตรวจสอบเงื่อนไขเพื่อมอบหมายงาน โดยลากเส้นตรงให้ñ่านจานวน “1” ทั้งหมดในตารางโดยใช้เส้นตรง จานวนน้อยเส้นที่สุด - ถ้าจานวนเส้นตรงที่ลากเท่ากับ n เส้น นั่นคือสามารถตัดสินใจมอบหมายงานจากตารางมอบหมายงานได้ - ถ้าจานวนเส้นตรงที่ลากน้อยกว่า n เส้น นั่นคือยังไม่สามารถตัดสินใจมอบหมายงานจากตารางมอบหมายได้ จาเป็นต้องดาเนินการปรับปรุงตารางมอบหมายงานเพื่อให้ดาเนินการตัดสินใจมอบหมายงานได้โดย 1. เลือกค่าใช้จ่ายต่าสุด   ij E โดยที่ ij E จะต้องไม่อยู่บนเส้นตรงใด ๆ 2. นา ij E หารสมาชิกแต่ทุกตัวในแถวที่ i หรือหลักที่ j àึ่งการปรับปรุงตารางมอบหมายงานจะทาให้เกิดจานวน “1” ในแถวหรือหลักของเมทริกà์อย่างน้อย 1 จานวนจากนั้น ดาเนินการขั้นตอนที่ 4 อีกครั้ง ขั้นตอนที่ ดาเนินการมอบหมายงานโดย Ghadle and Muley Rule [2] êัวอย่าง พิจารณาปัญหาค่าใช้จ่ายต่าสุดในการมอบหมายงาน 6 งาน ให้เครื่องจักร 6 เครื่องจักร โดยการปรับปรุงวิธีการ มอบหมายงานหนึ่งรูปแบบใหม่ êารางที่ǰ 2 ตารางแสดงค่าใช้จ่ายในการมอบหมายงาน 6 งาน ให้เครื่องจักร 6 เครื่องจักร งาน เครื่องจักร 1 2 3 4 5 6 1 20 23 18 10 16 20 2 50 20 17 16 15 11 3 60 30 40 55 8 7 4 6 7 10 20 25 9 5 18 19 28 17 60 70 6 9 10 20 30 40 55 ‡nµÄo‹nµ¥¦ª¤˜Îɵ»—°´œ—´°Š – ‡nµÄo‹nµ¥¦ª¤˜Îɵ»— ‡nµÄo‹nµ¥¦ª¤¼Š»— – ‡nµÄo‹nµ¥¦ª¤¼Š»—¦°Š¨Š¤µ