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

DOI10.1016/j.ipl.2009.02.007zbMath1214.68096OpenAlexW2005936117MaRDI QIDQ987835

Jinjiang Yuan, Cheng He, 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)

Related Items

Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan, BATCHING MACHINE SCHEDULING WITH BICRITERIA: MAXIMUM COST AND MAKESPAN, 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, Bounded serial-batching scheduling for minimizing maximum lateness and makespan, Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time

Cites Work

• Unnamed Item
• Unnamed Item
• Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan
• Scheduling a batching machine
• The complexity of one-machine batching problems
• Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time
• A multiple-criterion model for machine scheduling
• Multicriteria scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Single-Machine Scheduling to Minimize a Function of Two or Three Maximum Cost Criteria