← งานวิจัย COINล้างคิวทั้งหมดEnglish
COIN · ROSE · PERMUTATION OPTIMIZATION

ห้องทดลอง Parallel-Machine
Tardiness

จัดงานลงเครื่องจักรขนานที่เหมือนกันและเรียงงานภายในแต่ละเครื่อง โดยเข้ารหัสตัวแบ่งเครื่องจำนวน m−1 ตัวไว้ใน permutation โดยตรง เปรียบเทียบ total tardiness, maximum tardiness, makespan, completion time และความสมดุลของ load

ตัวประเมินเดียว · งบเท่ากันทุกอัลกอริทึมใช้ instance, evaluator, seed และจำนวน objective evaluations เดียวกัน ผลลัพธ์จึงตรวจสอบและทำซ้ำได้
StatusReady
Runs completed0 / 0
Evaluations—
Best primary—

Benchmark

ผลจะปรากฏหลังการทดลอง

Current: —

บทนำและแนวคิดของปัญหา

Parallel-machine tardiness ต่างจาก load balancing เพราะลำดับภายในเครื่องมีผลต่อเวลาสำเร็จและ tardiness ของแต่ละงาน งานที่เสร็จหลัง due date dⱼ มี Tⱼ=max(0,Cⱼ−dⱼ) การลดผลรวม Tⱼ จึงต้องตัดสินใจทั้ง assignment และ sequencing พร้อมกัน

representation แบบ separator ทำให้ COIN และ ROSE ใช้ permutation engine เดิมได้ โดย separator เป็น node จริงที่เรียนรู้ตำแหน่งและ adjacency ได้ อย่างไรก็ตาม separator ที่ต่างหมายเลขมีความหมายเชิงเครื่องเหมือนกัน จึงเป็น symmetry ที่ควรรายงานในงานวิจัย

การแทนคำตอบ

งาน: 0..n−1 · separator: n..n+m−2
π = (J3,J8,J2, |₁, J5,J7,J1, |₂, J6,J4,J9)

chromosome มีขนาด n+m−1 และมี separator ครบ m−1 ตัวเสมอ จึงถอดเป็น m machine sequences โดยไม่ต้อง repair อนุญาต empty machine หาก separator อยู่ติดกัน ซึ่ง evaluator จะสะท้อนผลผ่าน makespan และ load variance

นิยามปัญหา วัตถุประสงค์ และการคำนวณ fitness

ให้ pⱼ เป็น processing time, dⱼ เป็น due date, Cⱼ เป็น completion time บนเครื่องที่ได้รับมอบหมาย และ Lₖ เป็น load ของเครื่อง k

min f₁ = Σⱼ max(0,Cⱼ−dⱼ)
min f₂ = maxⱼ max(0,Cⱼ−dⱼ)
min f₃ = maxₖ Lₖ
min f₄ = Σⱼ Cⱼ
min f₅ = (1/m)Σₖ(Lₖ−L̄)²

single-objective track ใช้ total tardiness ตาม benchmark ดั้งเดิม ส่วน MO track แสดงความขัดแย้งระหว่าง tardiness, throughput และ balance ใช้ non-dominated sorting และรายงาน convergence, spread และ non-dominated ratio เช่นเดียวกับ Flow Shop Lab

ที่มาของ benchmark และวรรณกรรมที่เกี่ยวข้อง

Tanaka และ Araki เผยแพร่ benchmark สำหรับ identical parallel machines จำนวน 2–10 เครื่อง พร้อมผล optimum สำหรับขนาดที่รายงาน อย่างไรก็ตาม archive ต้นฉบับอยู่บน Google Drive และไม่ได้ถูกคัดลอกลง deployment นี้ ชุด preload ปัจจุบันจึงระบุอย่างตรงไปตรงมาว่าเป็น controlled fixtures ที่ใช้จำนวนงาน/เครื่องตาม benchmark ไม่ใช่ published instances เมื่อ archive พร้อม parser จะสามารถแทน fixture โดยไม่เปลี่ยน evaluator หรือ API

เอกสารอ้างอิง

  1. Tanaka Parallel-Machine Total Tardiness benchmark archive.
  2. Tanaka, S. & Araki, M. A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines. IJPE 113, 446–458 (2008).
  3. Graham et al. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics 5 (1979).