A DP algorithm for minimizing makespan and total completion time on a series-batching machine

DOI10.1016/J.IPL.2009.02.007MaRDI QIDQ987835zbMATH OpenOpenAlexFDO

Authors Cheng He, Jinjiang Yuan, Yanpei Liu

Publication date 16 August 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.02.007

zbMATH Keywords

computational complexitymakespanPareto optimal solutionstotal completion timemulticriteria schedulingseries-batching machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan
• Bicriteria scheduling on a series-batching machine to minimize makespan and total weighted completion time with equal length job
• Bicriteria scheduling of minimizing maximum lateness and makespan on a serial-batching machine
• Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan
• A bicriteria batch scheduling on a serial-batching machine

Cites work

• scientific article; zbMATH DE number 1634827 (Why is no real title available?)
• A multiple-criterion model for machine scheduling
• Bicriteria scheduling of minimizing maximum lateness and makespan on a serial-batching machine
• Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan
• Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time
• Multicriteria scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling a batching machine
• Single-Machine Scheduling to Minimize a Function of Two or Three Maximum Cost Criteria
• The complexity of one-machine batching problems

Cited in

(9)

• Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time
• Batching machine scheduling with bicriteria: maximum cost and makespan
• Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan
• Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan
• Bounded serial-batching scheduling for minimizing maximum lateness and makespan
• A bicriteria batch scheduling on a serial-batching machine
• A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling: a mixed graph coloring approach
• Improved algorithms for two-agent scheduling on an unbounded serial-batching machine
• Bicriteria scheduling on a series-batching machine to minimize makespan and total weighted completion time with equal length job

This page was built for publication: A DP algorithm for minimizing makespan and total completion time on a series-batching machine

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987835)