การจัดตารางเครื่องจักรแบบขนาน

การจัดตารางเครื่องจักรขนานคืออะไร?

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

กฎ LPT (Longest Processing Time) หรือการจ่ายงานที่ใช้เวลาดำเนินการนานที่สุดก่อน เป็นฮิวริสติกที่รู้จักกันดีสำหรับการทำให้ makespan บนเครื่องจักรขนานมีค่าน้อยที่สุด โดยเรียงงานตามเวลาดำเนินการจากมากไปน้อย แล้วมอบหมายแต่ละงานให้เครื่องจักรที่ว่างเร็วที่สุด LPT รับประกันว่า makespan จะไม่เกิน 4/3 เท่าของค่าที่ดีที่สุดสำหรับเครื่องจักรที่เหมือนกัน ส่วนกฎอื่น (SPT, EDD, WSPT) มุ่งตอบวัตถุประสงค์ที่ต่างออกไป

อัตราการใช้งานเครื่องจักร ซึ่งคือสัดส่วนของเวลาทั้งหมดที่เครื่องจักรแต่ละเครื่องมีงานทำ สะท้อนคุณภาพของการกระจายภาระงาน หากอัตราการใช้งานของทุกเครื่องเท่ากันแสดงว่าสมดุลดี ส่วนแผนภูมิแกนต์แสดงเส้นเวลาของตารางงานสำหรับเครื่องจักรแต่ละเครื่อง ทำให้มองเห็นเวลาว่างและความไม่สมดุลของภาระงานได้ทันที

Formula: Makespan = max(Completion Time of all machines) Utilization = Σ Processing Time / (Makespan x m) Tardiness = max(0, Completion - Due Date) LPT: Assign longest job to earliest available machine SPT: Assign shortest job to earliest available machine

ตัวอย่างการคำนวณ

งาน 4 งาน (p=8,6,5,3) บนเครื่องจักร 2 เครื่องด้วยกฎ LPT มอบหมาย Job1(8)→M1, Job2(6)→M2, Job3(5)→M2 (ภาระงาน 6→11), Job4(3)→M1 (ภาระงาน 8→11) ได้ makespan = 11 อัตราการใช้งาน: M1=11/11=100%, M2=11/11=100% นับว่าสมดุลอย่างสมบูรณ์ หากไม่ใช้ LPT แต่ใช้ FCFS แทน อาจได้ makespan=14 พร้อมกับความสมดุลที่แย่กว่า

เมื่อใดควรใช้เครื่องคำนวณนี้

• เมื่อจัดตารางกลุ่มงานข้ามเครื่องจักรหลายเครื่องที่เหมือนกันและต้องลด makespan หรือ total tardiness
• ระหว่างการวางแผนกำลังการผลิตเพื่อประเมินว่าการเพิ่มเครื่องจักรจะลด makespan ได้อย่างมีความหมายสำหรับปริมาณงานปัจจุบัน
• เมื่อเปรียบเทียบกฎการจัดส่งสำหรับงานผสมเฉพาะของคุณ — กฎต่างๆ หาค่าเหมาะสมของวัตถุประสงค์ต่างกันและตัวเลือกที่ดีที่สุดขึ้นกับลำดับความสำคัญ
• หลังจากเครื่องจักรเสียเพื่อจัดตารางงานที่เหลือใหม่ข้ามเครื่องจักรที่มีและประเมินผลกระทบการส่งมอบ
• เมื่อปรับสมดุลโหลดข้ามเครื่องจักรเพื่อลดเวลาว่างและให้เครื่องจักรทุกเครื่องมีส่วนร่วมเท่าเทียมกันในตารางการผลิต

ข้อผิดพลาดที่พบบ่อยที่ควรหลีกเลี่ยง

• ใช้ SPT สำหรับการลด makespan — SPT ลด average flow time ไม่ใช่ makespan ใช้ LPT สำหรับ makespan บนเครื่องจักรคู่ขนานซึ่งกำหนดงานที่ยาวที่สุดก่อน
• สมมติว่าเครื่องจักรเพิ่มลด makespan ตามสัดส่วนเสมอ — การปรับปรุงเป็นไปตามกฎ diminishing returns ด้วยขนาดงานที่ไม่เท่ากันมาก การเพิ่มเครื่องจักรอาจลด makespan ได้น้อยมาก
• ไม่พิจารณา release time เมื่องานมาถึงเวลาต่างกัน — กฎจัดส่งแบบ static สมมติว่างานทั้งหมดมีอยู่ที่เวลาศูนย์ ใช้การจัดส่งแบบ dynamic เมื่อเวลามาถึงแตกต่างกัน
• ละเลยสมดุลอัตราการใช้เครื่องจักร — ตารางที่มี makespan ต่ำสุดอาจทำให้บางเครื่องว่างเป็นเวลานาน ตรวจสอบอัตราการใช้ข้ามเครื่องจักรทุกเครื่องเพื่อความยุติธรรมและสมดุลการสึกหรอ

วิธีตีความผลลัพธ์

• อัตราการใช้เท่ากันข้ามเครื่องจักรทุกเครื่อง (>90% แต่ละเครื่อง) — โหลดสมดุลดี กฎจัดส่งทำงานมีประสิทธิภาพ
• เครื่องจักรหนึ่งใช้ 100% ขณะอื่นต่ำกว่ามาก — เครื่องนั้นเป็นคอขวด งานที่ยาวที่สุดน่าจะกำหนด makespan
• Total tardiness = 0 — งานทั้งหมดเสร็จก่อนวันกำหนดส่ง ตารางตรงตามคำมั่นสัญญาการส่งมอบทั้งหมด
• Total tardiness สูงกับงานที่ล่าช้าหลายงาน — ปริมาณงานเกินกำลังการผลิตภายในกรอบวันกำหนดส่ง พิจารณาทำงานล่วงเวลา เพิ่มเครื่องจักร หรือเจรจาขยายวันกำหนดส่ง
• LPT และ SPT ให้ makespan คล้ายกันมาก — เวลาประมวลผลงานค่อนข้างสม่ำเสมอ การเลือกกฎมีความสำคัญน้อยเมื่องานมีขนาดใกล้เคียงกัน

มาตรฐานและเอกสารอ้างอิงที่เกี่ยวข้อง

• APICS CPIM Body of Knowledge — ครอบคลุมแนวคิดการจัดตารางเครื่องจักรคู่ขนานภายในโมดูลการควบคุมกิจกรรมการผลิต
• ISA-95 (IEC 62264) — มาตรฐานการรวมระบบควบคุมองค์กรที่กำหนดระดับการจัดตารางรวมถึงการจัดตารางระดับเครื่องจักรโดยละเอียด

คำถามที่พบบ่อย

กฎการจ่ายงานแบบใดทำให้ makespan บนเครื่องจักรขนานมีค่าน้อยที่สุด

LPT (Longest Processing Time first) หรือการจ่ายงานที่ใช้เวลาดำเนินการนานที่สุดก่อน เป็นฮิวริสติกที่ดีที่สุดสำหรับการทำให้ makespan มีค่าน้อยที่สุด การมอบหมายงานที่ยาวที่สุดก่อนช่วยให้มั่นใจว่างานขนาดใหญ่จะไม่กลายเป็นคอขวดในช่วงท้าย LPT รับประกันคำตอบที่ไม่เกิน 4/3 - 1/(3m) เท่าของค่าที่ดีที่สุด โดย m คือจำนวนเครื่องจักร สำหรับเครื่องจักร 2 เครื่อง ค่านี้เท่ากับไม่เกิน 7/6 (≈17%) ของค่าที่ดีที่สุด

ควรจัดการอย่างไรกับงานที่มีเวลาพร้อมเริ่มหรือกำหนดส่งต่างกัน

เมื่อมีเวลาพร้อมเริ่ม งานจะเริ่มได้ก็ต่อเมื่อถึงเวลาพร้อมเริ่มของงานนั้นแล้วเท่านั้น จึงควรใช้การจ่ายงานแบบพลวัตที่ประเมินลำดับความสำคัญใหม่ทุกครั้งที่เครื่องจักรแต่ละเครื่องว่างลง เมื่อมีกำหนดส่ง กฎ EDD หรือ CR ช่วยลดความล่าช้าได้ สำหรับปัญหาซับซ้อนที่มีข้อจำกัดทั้งสองอย่าง ให้จำลองการใช้กฎหลายแบบแล้วเปรียบเทียบตัวชี้วัดสมรรถนะ กฎที่ดีที่สุดขึ้นอยู่กับส่วนผสมของงานและวัตถุประสงค์ในแต่ละกรณี