ตัวจำลองการจัดลำดับงาน

การจัดส่งงานคืออะไร?

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

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

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

Formula: SPT: Sort by processing time (ascending) LPT: Sort by processing time (descending) EDD: Sort by due date (ascending) CR: Sort by (Due Date - Now) / Processing Time WSPT: Sort by Weight / Processing Time (descending) Tardiness = max(0, Completion Time - Due Date)

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

งาน 3 งาน: A(p=4, d=10), B(p=2, d=8), C(p=6, d=12) ลำดับตาม SPT: B→A→C เวลาแล้วเสร็จ: 2, 6, 12 ความล่าช้า: 0+0+0=0 ลำดับตาม EDD: B→A→C (เหมือนกัน) ความล่าช้า=0 ลำดับตาม LPT: C→A→B เวลาแล้วเสร็จ: 6, 10, 12 ความล่าช้า: 0+0+4=4 ในกรณีนี้ SPT ให้ผลดีที่สุด

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

• เมื่อประเมินว่ากฎการจัดส่งใดลด total tardiness ได้น้อยที่สุดสำหรับงานปัจจุบันก่อนนำมาใช้บนพื้นที่การผลิต
• ระหว่างการประชุมวางแผนการผลิตเพื่อจำลองว่ากฎลำดับความสำคัญต่างๆ จะเรียงลำดับคิวงานปัจจุบันอย่างไร
• เมื่อฝึกอบรมหัวหน้างานเกี่ยวกับการแลกเปลี่ยนระหว่างกลยุทธ์การจัดส่งต่างๆ และผลกระทบต่อประสิทธิภาพการส่งมอบ
• หลังจากเกิดการหยุดชะงักตารางการผลิต (เครื่องเสีย คำสั่งเร่งด่วน) เพื่อเรียงลำดับงานที่เหลือใหม่และลดผลกระทบการส่งมอบ
• เมื่อเปรียบเทียบกฎการจัดตารางแบบฮิวริสติกซ์เพื่อเลือกกฎที่ดีที่สุดสำหรับลักษณะ job shop ที่เกิดขึ้นซ้ำ

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

• ใช้ SPT เพื่อลด tardiness — SPT ลด average flow time ไม่ใช่ tardiness ใช้ EDD สำหรับการลด maximum tardiness หรือกฎ weighted tardiness สำหรับวัตถุประสงค์ที่เน้นวันกำหนดส่ง
• ใช้ FCFS เป็นค่าเริ่มต้นเพราะดู 'ยุติธรรม' — FCFS มักให้ผลลัพธ์แย่ที่สุดในเกือบทุกตัวชี้วัด ควรใช้เมื่อลำดับความสำคัญของงานเท่ากันจริงๆ และลำดับคำสั่งมีความสำคัญเท่านั้น
• ไม่อัปเดตการตัดสินใจจัดส่งเมื่อเงื่อนไขเปลี่ยน — กฎการจัดส่งควรประเมินใหม่เมื่อมีงานใหม่ งานถูกยกเลิก หรือเครื่องจักรเสีย
• ละเลยน้ำหนักงานเมื่อลำดับความสำคัญต่างกัน — หากบางงานสำคัญกว่า (ลูกค้ามูลค่าสูง เงื่อนไขปรับ) ใช้ WSPT หรือ CR แทน SPT หรือ EDD ธรรมดา

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

• บนเครื่องจักรเดียวที่งานทั้งหมดถูกปล่อยที่เวลา 0 ค่า makespan จะเท่ากันทุกกฎ (เครื่องไม่เคยว่าง) — ให้ตัดสินกฎด้วยความล่าช้ารวม ไม่ใช่ makespan เพราะ makespan จะต่างกันเฉพาะเมื่อเวลามาถึงบังคับให้เกิดช่องว่างเครื่องว่าง
• ความล่าช้ารวมเท่ากับ 0 หมายความว่าทุกงานทันวันครบกำหนดภายใต้กฎนั้น — ตรวจดูแผนภูมิ Gantt ว่าเหลือเวลาเผื่อก่อนวันครบกำหนดเท่าใดเพื่อประเมินความทนทานต่อการหยุดชะงัก
• ในมุมมองเปรียบเทียบทุกกฎ ให้เลือกกฎที่มีความล่าช้ารวมต่ำสุดสำหรับชุดงานของคุณ — เมื่อหลายกฎได้ผลเท่ากัน ให้เลือกกฎที่ง่ายกว่า (เช่น EDD แทน CR) สำหรับการปฏิบัติหน้างาน
• ใช้คอลัมน์ความล่าช้ารายงานเพื่อหาว่าออเดอร์ใดล่าช้า — หากงานล่าช้าหลักงานเดียวเป็นตัวขับยอดรวม การเจรจาวันครบกำหนดใหม่เพียงรายการเดียวอาจดีกว่าการเปลี่ยนกฎการจัดลำดับ
• WSPT ต่างจาก SPT เฉพาะเมื่อน้ำหนักงานต่างกัน และ CR ต่างจาก EDD เฉพาะเมื่อเวลาประมวลผลแปรผันเทียบกับเวลาเผื่อวันครบกำหนด — หากผลลัพธ์เหมือนกันทุกกฎ ข้อมูลงานของคุณอาจยังไม่ได้ใช้ประโยชน์จากอินพุตเหล่านั้น

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

• APICS CPIM Body of Knowledge — โมดูลการควบคุมกิจกรรมการผลิตที่ครอบคลุมกฎการจัดส่งและการจัดตารางพื้นที่การผลิต
• ISA-95 (IEC 62264) — มาตรฐานการรวมระบบควบคุมองค์กรที่กำหนดลำดับชั้นฟังก์ชันการจัดตารางและการจัดส่ง

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

ฉันควรใช้กฎการจัดลำดับงาน (dispatching rule) แบบใด?

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

ทำไมจึงไม่ใช้อัลกอริทึมการจัดตารางแบบหาค่าเหมาะที่สุดแทนกฎการจ่ายงาน

การจัดตารางแบบหาค่าเหมาะที่สุด (เช่น วิธีแตกกิ่งและจำกัดขอบเขต หรือ MIP) เป็นปัญหาระดับ NP-hard สำหรับปัญหาจริงส่วนใหญ่ เวลาในการคำนวณเพิ่มขึ้นแบบเลขชี้กำลังตามจำนวนงาน ขณะที่กฎการจ่ายงานทำงานด้วยเวลา O(n log n) และรองรับการเข้ามาของงานแบบพลวัต เครื่องจักรเสีย และการเปลี่ยนลำดับความสำคัญได้แบบทันเวลาจริง ในทางปฏิบัติ กฎการจ่ายงานที่ออกแบบมาดีให้ผลห่างจากค่าเหมาะที่สุดเพียง 5-15% ในปัญหาส่วนใหญ่