กราฟการไหลที่มีขอบเขตล่างที่ไม่ใช่ศูนย์หรือความจุ 0
ฉันกลัวว่าชื่อคำถามอาจไม่ถูกต้องเพียงพอ แต่ฉันไม่สามารถหาสิ่งที่ถูกต้องกว่านี้ได้
นี่คือปัญหา
รับเครื่อง 'n'
- แต่ละเครื่องมีชุดความสามารถ
- แต่ละเครื่องมีความพร้อมใช้งานสูงสุด (A (m))
รับงาน 'm'
- แต่ละงานต้องใช้ชุดความสามารถ
- แต่ละงานใช้เวลาที่แน่นอน (D (t))
- งานจะต้องดำเนินการในเครื่องเดียวเท่านั้น
ปัญหาคือการพิจารณาว่างานทั้งหมดจะเสร็จสมบูรณ์ได้หรือไม่
ฉันติดขัดกับข้อกำหนด 'เครื่องเดียวเท่านั้น' โฟลว์กราฟเดียวที่ฉันสามารถทำได้ไม่รับประกันว่างานจะไม่เชื่อมโยงกับเครื่องจักรมากกว่าหนึ่งเครื่อง
เป็นปัญหาการจับคู่แบบสองฝ่าย แต่มีความจุ> 1
ฉันยังพบพฤติกรรมคล้าย XOR ในเครือข่ายโฟลว์ซึ่งคล้ายกัน แต่มีข้อกำหนด 'xor' ในส่วนท้าย 'แหล่งที่มา' ซึ่งฉันต้องการในส่วนท้ายเป้าหมาย
ใครจะมีเคล็ดลับ? เป็นไปได้ไหมที่จะจำลองสิ่งนี้เป็นกราฟการไหล
Tx!
ปีเตอร์
ปล. พยายามชี้แจงข้อกำหนดด้วยตัวอย่างที่เป็นรูปธรรมมากขึ้น
สมมติระบบการพิมพ์ดิจิทัลและงานพิมพ์
- การกดแบบดิจิทัลแต่ละครั้งสามารถทำงานได้หลายชั่วโมง
- การกดแต่ละครั้งมีความเป็นไปได้ในการตกแต่ง: เช่น 'เครื่องตัดแผ่น', 'ลามิเนต', 'เครื่องตัดเลเซอร์', 'การพับกระดาษ', ....
- งานพิมพ์แต่ละงานต้องใช้เวลาหลายชั่วโมง
- งานพิมพ์แต่ละงานต้องการความเป็นไปได้ในการตกแต่งอย่างน้อยหนึ่งอย่าง
ด้วยชุดเครื่องความพร้อมใช้งานสำหรับแต่ละชิ้นและความเป็นไปได้ในการตกแต่งและชุดงานพิมพ์ (ระยะเวลาตัวเลือกการตกแต่งที่จำเป็น) กำหนดว่างานพิมพ์ทั้งหมดสามารถเสร็จสิ้นได้หรือไม่
เช่น
- เครื่องพิมพ์ p1 ใช้งานได้เป็นเวลา 10 ชั่วโมงและมีคุณสมบัติ f1 และ f2
- เครื่องพิมพ์ p2 ใช้งานได้เป็นเวลา 10 ชั่วโมงและมีคุณสมบัติ f2 และ f3
- Job1 ซึ่งต้องการคุณสมบัติ f1 และ f2 ใช้เวลา 8 ชั่วโมงในการรัน
- Job2 ซึ่งต้องการคุณสมบัติ f2 และ f3 ใช้เวลา 8 ชั่วโมงในการรัน
- Job3 ที่ต้องการฟีเจอร์ f2 ต้องใช้เวลา 4 ชั่วโมงในการรัน
เครื่องพิมพ์ที่พร้อมใช้งานเช่น 10 ชั่วโมงสามารถทำงานได้ 10 x 1 ชั่วโมงหรืองาน 5 x 2 ชั่วโมงหรืองาน 1 x 8 ชม. และงาน 1 x 2 ชม. ... งานจะต้องทำงานบนเครื่องพิมพ์เครื่องเดียวเสมอ
โฟลว์ไดอะแกรมที่ฉันคิดขึ้นได้มักจะส่งผลในกรณีที่
8 ชั่วโมงของ p1 ถูกกำหนดให้กับ job1 (ทิ้งไว้ 2 ชั่วโมงสำหรับเครื่องพิมพ์ p1) 8 ชั่วโมงของ p2 ถูกกำหนดให้กับ job2 (ทิ้งไว้ 2 ชั่วโมงสำหรับเครื่องพิมพ์ p2)
(จนถึงตอนนี้ดีมาก)
แต่แล้ว
2 ชั่วโมงของ p1 และ p2 ที่เหลือจะใช้ในการไหลไปที่ job3 และการไหลสูงสุดดูเหมือนจะบ่งบอกว่าสามารถรันงานทั้งสามได้ (ซึ่งไม่โอเค)
คำตอบ
ปัญหาของคุณคือ NP-hard ในกรณีพิเศษที่ไม่มีงานใดต้องการคุณสมบัติเฉพาะและเครื่องพิมพ์ทั้งหมดมีความพร้อมใช้งานเท่ากันปัญหานี้จะกลายเป็นเพียงปัญหาการบรรจุถังขยะซึ่งเป็น (อย่างยิ่ง) NP-complete
คุณสามารถลองปรับอัลกอริทึมมาตรฐานสำหรับการบรรจุถังขยะให้เข้ากับสถานการณ์ของคุณ ตัวอย่างเช่นแนวทางหนึ่งคือใช้การเขียนโปรแกรมเชิงเส้นจำนวนเต็มและหวังว่าตัวแก้ ILP จะสามารถจัดการกับปัญหาที่เกิดขึ้นได้