Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Lịch trình đa tiêu chí trên máy theo lô nối tiếp nhằm tối thiểu hóa chi phí tối đa và thời gian hoàn thành
Tóm tắt
Bài báo này nghiên cứu vấn đề đa tiêu chí trong việc lập lịch n công việc trên một máy theo lô nối tiếp nhằm tối thiểu hóa đồng thời chi phí tối đa và thời gian hoàn thành. Một máy theo lô nối tiếp là một máy có thể xử lý tối đa b công việc trong một lô, và các công việc trong một lô bắt đầu và hoàn thành tại cùng một thời điểm, trong đó thời gian xử lý của một lô bằng tổng thời gian xử lý của các công việc trong lô đó. Khi một lô mới bắt đầu, sẽ có một khoảng thời gian thiết lập cố định s. Chúng tôi giới hạn nghiên cứu trong mô hình không giới hạn, trong đó b ≥ n. Chúng tôi trình bày một thuật toán thời gian đa thức để tìm tất cả các giải pháp Pareto tối ưu cho vấn đề lập lịch đa tiêu chí này.
Từ khóa
#lập lịch #máy theo lô #chi phí tối đa #thời gian hoàn thành #giải pháp ParetoTài liệu tham khảo
Agnetis A, Mirchani PB, Pacciarell D, Pacifici A (2004) Scheduling problems with two competing agents. Oper Res 52: 229–242
Baker KR, Smith JC (2003) A multiple-criterion model for machine scheduling. J Sched 6: 7–16
Brucker P (2001) Scheduling algorithms, 3rd edn. Springer, Berlin
Graham RL, Lawler EL, Lenstra JK, Kan AHGR (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discret Math 5: 287–326
He C, Lin YX, Yuan JJ (2007) Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. Theoret Comput Sci 381: 234–240
He C, Lin YX, Yuan JJ (2008) Bicriteria scheduling of minimizing maximum lateness and makespan on a serial-batching machine. Found Comput Decis Sci 33: 369–376
He C, Lin YX, Yuan JJ (2009) A DP algorighm for minimizing makespan and total completion time on a series-batching machine. Inf Process Lett 109: 603–607
Hoogeveen H (2005) Multicriteria scheduling. Eur J Oper Res 167: 592–623
Hoogeveen JA (1996) Single-machine Scheduling to minimize a function of two or three maximum cost criteria. J Algorithms 21: 415–433
Hoogeveen JA, Van de Velde SL (1995) Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time. Oper Res Lett 17: 205–208
Webster S, Baker KR (1995) Scheduling groups of jobs on a single machine. Oper Res 43: 692–703