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

ห้องทดลองจัดตาราง
ภายใต้ลำดับก่อน–หลัง

จัดลำดับกิจกรรมที่มีทั้ง precedence constraints และทรัพยากรหมุนเวียนจำกัด ด้วย priority-list permutation และ Serial Schedule Generation Scheme แล้วเปรียบเทียบ Pareto trade-off ระหว่างเวลาโครงการ ความล่าช้า เวลาสำเร็จรวม และความเรียบของการใช้ทรัพยากร

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

Benchmark

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

Current: —

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

Precedence-constrained scheduling พบในโครงการก่อสร้าง การพัฒนาซอฟต์แวร์ งานวิจัย การผลิตแบบโครงการ และ workflow ทางธุรกิจ กิจกรรมหนึ่งเริ่มไม่ได้จนกว่างานก่อนหน้าจะเสร็จ และถึงแม้ precedence จะอนุญาตให้เริ่มได้ งานก็ยังต้องรอหากกำลังคน เครื่องจักร หรือทรัพยากรอื่นไม่พอ

ห้องทดลองนี้ใช้แบบจำลอง RCPSP แบบ single-mode และ non-preemptive: แต่ละกิจกรรมมีระยะเวลาคงที่ ใช้ทรัพยากรหมุนเวียนจำนวนหนึ่งตลอดช่วงทำงาน และหยุดกลางคันไม่ได้ จุดสำคัญคือ evaluator ไม่ลงโทษคำตอบที่ผิดด้วย penalty แต่ใช้ decoder สร้างเฉพาะตารางที่ถูกต้องทั้ง precedence และ capacity เสมอ จึงไม่มี trade-off ปลอมระหว่าง “ผิดข้อจำกัดน้อยลง” กับ objective ทางธุรกิจ

การแทนคำตอบ

chromosome π = permutation ของ activity IDs
decoder: eligible set → เลือกกิจกรรมที่ rank ใน π สูงสุด → วางที่เวลา feasible เร็วที่สุด

Permutation ไม่ได้แปลว่า “รันตามลำดับนี้ตรง ๆ” แต่เป็น priority list หาก activity ลำดับแรกยังติด predecessor ตัวถัดไปที่ eligible จะถูกเลือกก่อน เมื่อ predecessor เสร็จ activity เดิมจึงกลับเข้าสู่ชุดผู้สมัคร วิธีนี้ทำให้ COIN, ROSE, HBSA และ permutation GA ใช้ representation เดียวกันโดยไม่ต้อง repair DAG

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

ให้ pⱼ เป็นระยะเวลา rⱼₖ เป็นความต้องการทรัพยากร k, Rₖ เป็น capacity, Pⱼ เป็นชุด predecessor, Sⱼ และ Cⱼ เป็นเวลาเริ่มและเสร็จ

Cᵢ ≤ Sⱼ ∀ i∈Pⱼ
Σⱼ∈A(t) rⱼₖ ≤ Rₖ ∀k,t
min f₁ = Cmax
min f₂ = Σⱼ max(0,Cⱼ−dⱼ)
min f₃ = maxⱼ max(0,Cⱼ−dⱼ)
min f₄ = Σⱼ Cⱼ
min f₅ = meanₖ Varₜ(Uₖ(t)/Rₖ)

Makespan ลดเวลาปิดโครงการ, total/maximum tardiness คุม due date, total completion time ส่งเสริมให้กิจกรรมจำนวนมากเสร็จเร็ว และ resource variance ลดการแกว่งของ utilization การเลือก 2–3 objective เปิดให้ NSGA-II, SPEA2, NSGA-III และ MO-COIN เรียนชุดคำตอบ non-dominated ภายใต้งบ evaluation เดียวกัน

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

PSPLIB ของ Kolisch และ Sprecher เป็นมาตรฐานหลักของ RCPSP มีชุด j30, j60, j90 และ j120 พร้อม lower bounds, heuristic solutions และ optimum ที่พิสูจน์แล้วบางส่วน หน้า lab เริ่มด้วย controlled fixtures ขนาดเล็กเพื่อให้สอนได้รวดเร็วและระบุแหล่งที่มาตรงไปตรงมา; data model และ priority-list SGS ถูกออกแบบให้รองรับการเพิ่ม parser สำหรับไฟล์ PSPLIB .sm ต่อไป

วิธีดั้งเดิมเริ่มจาก Critical Path Method และ priority rules เช่น shortest processing time, minimum slack และ greatest resource demand จากนั้นพัฒนาเป็น branch-and-bound, constraint programming, time-indexed MILP, genetic algorithms, simulated annealing, tabu search, ant colony optimization, particle swarm และ permutation EDAs งานเปรียบเทียบควรแยกคุณภาพ search ออกจาก decoder: ทุกวิธีในหน้านี้จึงใช้ SGS instance เดียวและวัดด้วย objective evaluations เท่ากัน

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

  1. PSPLIB — Project Scheduling Problem Library.
  2. Kolisch, R. & Sprecher, A. (1997). PSPLIB — A project scheduling problem library. European Journal of Operational Research, 96(1), 205–216. DOI.
  3. Hartmann, S. & Kolisch, R. (2000). Experimental evaluation of state-of-the-art heuristics for the RCPSP. EJOR, 127, 394–407.
  4. Kolisch, R. (1996). Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. EJOR, 90, 320–333.