การจัดตารางการผลิตแบบ Job Shop
- ผู้เสนอ
- Pinedo, M. L.
- ปี
- 2016
- ประเภท
- Combinatorial scheduling problem
- กลุ่มวิธี
- Optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การจัดตารางการผลิตแบบ Job Shop (Job Shop Scheduling) คือปัญหาในการกำหนดชุดของงาน (tasks) ให้กับชุดของเครื่องจักร (resources) ตลอดช่วงเวลาหนึ่ง ภายใต้ข้อจำกัดด้านลำดับก่อนหลังและขีดความสามารถ โดยมีเป้าหมายเพื่อเพิ่มประสิทธิภาพของตัวชี้วัดต่างๆ เช่น makespan (เวลาที่ใช้ในการผลิตทั้งหมด), ความล่าช้า หรือต้นทุน ปัญหา Job Shop เป็นปัญหาการหาค่าเหมาะสมเชิงการจัดหมู่ (combinatorial optimization problem) แบบคลาสสิกในสาขาวิจัยดำเนินงาน (operations research) ซึ่งสามารถแก้ไขได้ด้วยวิธีการฮิวริสติกส์ (heuristics) เช่น กฎการจัดส่งแบบโลภ (greedy dispatching rules), simulated annealing, genetic algorithms และอัลกอริทึมแบบแม่นยำ (exact algorithms) เช่น branch-and-bound, constraint programming ปัญหานี้เป็นพื้นฐานสำคัญในการผลิต การบริหารโครงการ และการจัดตารางการทำงานด้วยคอมพิวเตอร์
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการถึงโรงกลึงขนาดเล็กที่มีเครื่องจักร 10 เครื่อง คำสั่งซื้อของลูกค้า (งาน) ประกอบด้วยชิ้นส่วน 5 ชิ้น แต่ละชิ้นต้องผ่านลำดับการปฏิบัติงานบนเครื่องจักรที่แตกต่างกัน: ชิ้นส่วนที่ 1 ต้องผ่านการกลึงบนเครื่องจักร A จากนั้นจึงเจาะบนเครื่องจักร C ชิ้นส่วนที่ 2 ต้องผ่านการเจาะบนเครื่องจักร B จากนั้นจึงเชื่อมบนเครื่องจักร D ชิ้นส่วนทั้งหมดจะถูกนำมารวมกันเพื่อประกอบขั้นสุดท้าย ความท้าทายคือ: จัดตารางการปฏิบัติงานทั้งหมดเพื่อลดเวลาการผลิตรวมให้เหลือน้อยที่สุด โดยไม่เกินขีดความสามารถของเครื่องจักร และต้องเคารพลําดับการปฏิบัติงานของแต่ละชิ้นส่วน หากคุณกำหนดให้ชิ้นส่วนที่ 1 ไปยังเครื่องจักร A ช้าเกินไป เครื่องจักร C จะว่างงาน หากคุณใช้งานเครื่องจักร C มากเกินไป ทุกอย่างจะติดขัด ปัญหา Job Shop แสดงถึงความซับซ้อนนี้: ด้วยงาน 100 งานและเครื่องจักร 20 เครื่อง จำนวนตารางที่เป็นไปได้มีมหาศาล ทำให้การหาคำตอบที่แม่นยำไม่สามารถทำได้ ในทางกลับกัน คุณจะใช้ฮิวริสติกส์เพื่อค้นหาตารางที่ดี (ไม่จำเป็นต้องเหมาะสมที่สุด) ได้อย่างรวดเร็ว
ประวัติศาสตร์
ปัญหาการจัดตารางการผลิตแบบ Job Shop เกิดขึ้นในปี 1950 ในฐานะปัญหาการวิจัยในสาขาวิจัยดำเนินงาน ผลงานบุกเบิกโดย Johnson (1954) ได้แก้ปัญหาเครื่องจักรสองเครื่องได้อย่างเหมาะสมที่สุด; Fisher และ Thompson (1963) ได้สร้างปัญหามาตรฐานที่ยังคงใช้มาจนถึงปัจจุบัน ปัญหานี้เป็น NP-hard (พิสูจน์แล้วในปี 1970) ซึ่งกระตุ้นให้เกิดการพัฒนาฮิวริสติกส์และเมตาฮิวริสติกส์ แนวทางที่ทันสมัยรวมถึง constraint programming (1990s–2000s), genetic algorithms และวิธีการแบบผสมผสาน ปัจจุบันการจัดตารางการผลิตแบบ Job Shop เป็นสาขาที่พัฒนาแล้วซึ่งมีการประยุกต์ใช้นอกเหนือจากการผลิตไปสู่คลาวด์คอมพิวติ้ง โทรคมนาคม และการขนส่ง
ควรใช้เมื่อใด
การจัดตารางการผลิตแบบ Job Shop สามารถนำไปใช้ได้กับสภาพแวดล้อมการผลิตหรือบริการใดๆ ที่มีเครื่องจักร/ทรัพยากรหลายเครื่อง และงานที่มีลำดับการปฏิบัติงานที่แตกต่างกัน การใช้งานทั่วไป ได้แก่ โรงกลึง โรงพิมพ์ การผลิตแผ่นเวเฟอร์เซมิคอนดักเตอร์ โรงพยาบาล (การจัดตารางห้องผ่าตัด) และการจัดตารางโครงการ ใช้เมื่อความซับซ้อนของงานสูง (หลายการปฏิบัติงานต่องาน), การใช้เครื่องจักรมีความสำคัญอย่างยิ่ง หรือวันครบกำหนดกระชั้นชิด มีความสำคัญน้อยกว่าในสภาพแวดล้อมสายการประกอบ (การไหลเชิงเส้น) หรือการปฏิบัติงานแบบเครื่องจักรเดี่ยวที่เรียบง่าย
ข้อจำกัดและข้อควรพิจารณา
- ความซับซ้อนเชิงการจัดหมู่: การค้นหาคำตอบที่เหมาะสมที่สุดเป็นปัญหา NP-hard; การแก้ปัญหาในทางปฏิบัติจำเป็นต้องใช้ฮิวริสติกส์ที่อาจไม่เหมาะสมที่สุดในระดับสากล
- คำตอบแบบฮิวริสติกส์ขึ้นอยู่กับบริบท; กฎที่ใช้ได้ดีกับร้านค้าหนึ่งอาจทำงานได้ไม่ดีในอีกร้านหนึ่ง ซึ่งต้องมีการปรับแต่งและตรวจสอบความถูกต้อง
- สมมติว่าข้อมูลนำเข้าเป็นแบบคงที่ (งานและเครื่องจักรคงที่); ร้านค้าจริงประสบกับการมาถึงของงานแบบไดนามิก การยกเลิก และความล้มเหลวของอุปกรณ์ ซึ่งต้องมีการจัดตารางใหม่บ่อยครั้ง
- ความเสถียรของตาราง: การเปลี่ยนแปลงตารางบ่อยครั้ง (เนื่องจากงานใหม่หรือการหยุดชะงัก) อาจเพิ่มต้นทุนและทำให้การประสานงานกับพนักงานและลูกค้าซับซ้อนขึ้น
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- รองรับข้อจำกัดที่ซับซ้อนและสมจริง (ลำดับก่อนหลัง, ความสามารถของเครื่องจักร, วันครบกำหนด) ที่กฎการจัดตารางแบบง่ายไม่สามารถจัดการได้
- ปรับให้เหมาะสมกับตัวชี้วัดทางธุรกิจที่เกี่ยวข้อง (makespan, ความล่าช้า, การใช้เครื่องจักร) แทนที่จะเป็นกฎเฉพาะกิจ
- ช่วยให้ตอบสนองต่อการหยุดชะงักได้อย่างรวดเร็ว; อัลกอริทึมการจัดตารางใหม่สามารถสร้างแผนที่แก้ไขได้เมื่อเครื่องจักรเสียหรือมีงานเร่งด่วนเข้ามา
- การกำหนดสูตรทางคณิตศาสตร์ช่วยให้สามารถวิเคราะห์ความไวและสำรวจการแลกเปลี่ยน (เช่น ความล่าช้าเทียบกับ makespan)
- ได้รับการสนับสนุนโดยเครื่องมือซอฟต์แวร์ที่มีประสิทธิภาพและอัลกอริทึมเมตาฮิวริสติกส์ที่พัฒนาแล้ว
การประยุกต์ใช้
- โรงกลึงที่มีความแม่นยำใช้การจัดตารางการผลิตแบบ Job Shop ร่วมกับ simulated annealing เพื่อจัดตารางชิ้นส่วนที่กำหนดเองกว่า 200 ชิ้นบนเครื่องจักร CNC 15 เครื่อง ลด makespan ลง 15 เปอร์เซ็นต์ และปรับปรุงการส่งมอบตรงเวลาจาก 85 เปอร์เซ็นต์เป็น 95 เปอร์เซ็นต์
- โรงงานผลิตเซมิคอนดักเตอร์ใช้การจัดตารางแบบ constraint-based เพื่อจัดการขั้นตอนกระบวนการกว่า 500 ขั้นตอนบนเครื่องมือ 50 ชิ้น ลดเวลาวงจรของแผ่นเวเฟอร์ให้เหลือน้อยที่สุด และลดสินค้าคงคลังระหว่างผลิตลง 20 เปอร์เซ็นต์
- บริษัทสิ่งพิมพ์ใช้การจัดตารางการผลิตแบบ Job Shop แบบไดนามิกเพื่อกำหนดงานพิมพ์ให้กับเครื่องพิมพ์ 8 เครื่องที่มีความสามารถแตกต่างกัน โดยปรับให้เหมาะสมกับส่วนผสมของงาน (ปริมาณมากเทียบกับงานพิเศษ) และลดเวลาการเปลี่ยนงานให้เหลือน้อยที่สุด
- ทีมจัดตารางของโรงพยาบาลใช้ Job Shop algorithms สำหรับการจัดตารางห้องผ่าตัด ประสานงานศัลยแพทย์ ทีมผ่าตัด และอุปกรณ์ ปรับปรุงการใช้ห้องผ่าตัดจาก 65 เปอร์เซ็นต์เป็น 82 เปอร์เซ็นต์
วิธีการทำงาน
วิธีการทำงาน
กำหนดงาน (คำสั่งซื้อ, ภารกิจ) พร้อมลำดับการปฏิบัติงาน, ข้อกำหนดเครื่องจักร, เวลาดำเนินการ และวันครบกำหนด กำหนดเครื่องจักรที่มีอยู่และช่วงเวลาที่พร้อมใช้งาน
ระบุข้อจำกัด: ลำดับการปฏิบัติงาน (ชิ้นส่วนที่ 1 ต้องเสร็จสิ้นการปฏิบัติงาน A ก่อนเริ่มการปฏิบัติงาน B), ขีดความสามารถ (เครื่องจักรแต่ละเครื่องสามารถประมวลผลงานได้ครั้งละหนึ่งงาน) และทางเลือกอื่นๆ เช่น เวลาปล่อยงานและวันครบกำหนด
ใช้กฎการจัดส่ง (dispatching rule) (เช่น เวลาดำเนินการที่สั้นที่สุด, วันครบกำหนดที่เร็วที่สุด, อัตราส่วนวิกฤต) เพื่อจัดลำดับงานในแต่ละเครื่องจักร สร้างตารางเริ่มต้น
ใช้เมตาฮิวริสติกส์ (metaheuristics) (simulated annealing, tabu search, genetic algorithms, ant colony optimization) เพื่อปรับปรุงตารางผ่านการค้นหาเฉพาะที่ (local search) หรือวิธีการแบบประชากร (population-based methods)
ประเมินคุณภาพของตาราง (makespan, ความล่าช้า, เวลาว่าง, เวลาบัฟเฟอร์) หากยอมรับได้ ให้ดำเนินการ มิฉะนั้น ให้ปรับพารามิเตอร์และปรับให้เหมาะสมอีกครั้ง
ข้อผิดพลาดที่พบบ่อย
- การปรับให้เหมาะสมกับตัวชี้วัดที่ไม่ถูกต้อง; การเพิ่มการใช้เครื่องจักรให้สูงสุดอาจเพิ่มความล่าช้าของงาน ในขณะที่การปฏิบัติตามวันครบกำหนดทั้งหมดอาจต้องใช้เวลาว่างจำนวนมาก
- การละเลยเวลาตั้งค่าและการเปลี่ยนงาน; ตารางที่ลดเวลาว่างให้เหลือน้อยที่สุดแต่ต้องมีการตั้งค่าบ่อยครั้งและใช้เวลานานอาจไม่เหมาะสมที่สุดในทางปฏิบัติ
- การเชื่อมั่นในตารางฮิวริสติกส์มากเกินไปโดยไม่มีการตรวจสอบความถูกต้องกับพฤติกรรมของร้านค้าจริง; ข้อจำกัดมักจะซับซ้อนกว่าที่แบบจำลองจับได้
คำถามที่พบบ่อย
Makespan คืออะไร และทำไมจึงสำคัญ?
Makespan คือเวลาทั้งหมดตั้งแต่เริ่มต้นการปฏิบัติงานแรกจนถึงการเสร็จสิ้นการปฏิบัติงานสุดท้าย มีความสัมพันธ์โดยตรงกับการใช้ประโยชน์จากอุปกรณ์ กระแสเงินสด (การเสร็จสิ้นที่เร็วขึ้น = การชำระเงินที่เร็วขึ้น) และความพึงพอใจของลูกค้า การลด makespan ให้เหลือน้อยที่สุดเป็นวัตถุประสงค์หลักทั่วไปในการจัดตารางการผลิตแบบ Job Shop
ความแตกต่างระหว่างการจัดตารางการผลิตแบบ Job Shop แบบสถิตและแบบไดนามิกคืออะไร?
การจัดตารางแบบสถิติ (Static scheduling) สมมติว่างานทั้งหมดเป็นที่ทราบล่วงหน้า; คุณปรับชุดงานที่กำหนดไว้ การจัดตารางแบบไดนามิก (Dynamic scheduling) จัดการกับงานที่มาถึงตลอดเวลา; ตารางจะถูกแก้ไขเมื่อมีงานใหม่เข้ามาหรือเกิดการหยุดชะงัก ร้านค้าส่วนใหญ่ในความเป็นจริงเป็นแบบไดนามิก ซึ่งต้องใช้อัลกอริทึมการปรับให้เหมาะสมใหม่อย่างรวดเร็ว
เราควรใช้กฎการจัดส่ง (dispatching rule) ใด?
ไม่มีกฎใดกฎหนึ่งที่โดดเด่น เวลาดำเนินการที่สั้นที่สุด (Shortest Processing Time - SPT) ลด makespan ให้เหลือน้อยที่สุด; วันครบกำหนดที่เร็วที่สุด (Earliest Due Date - EDD) ลดความล่าช้าให้เหลือน้อยที่สุด; อัตราส่วนวิกฤต (Critical Ratio) สร้างสมดุลระหว่างทั้งสอง ทดสอบกฎด้วยข้อมูลในอดีตหรือการจำลองเพื่อค้นหาสิ่งที่เหมาะสมที่สุดสำหรับลำดับความสำคัญและข้อจำกัดของร้านค้าของคุณ
การจัดตารางการผลิตแบบ Job Shop สามารถจัดการทักษะของพนักงานและการฝึกอบรมข้ามสายงานได้หรือไม่?
ได้ โดยการขยายแบบจำลองทรัพยากร: แทนที่จะเป็นเพียง 'เครื่องจักร A' ให้ระบุ 'เครื่องจักร A พร้อมพนักงาน 1' หรือ 'เครื่องจักร A พร้อมพนักงาน 2' อย่างไรก็ตาม สิ่งนี้จะเพิ่มความซับซ้อนของปัญหา; ตรวจสอบให้แน่ใจว่าซอฟต์แวร์การจัดตารางของคุณรองรับข้อจำกัดหลายทรัพยากร
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วTaillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว