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

DOI10.1016/J.IPL.2009.02.007zbMATH Open1214.68096OpenAlexW2005936117MaRDI QIDQ987835FDOQ987835

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

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

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)

Cites Work

• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling a batching machine
• A multiple-criterion model for machine scheduling
• The complexity of one-machine batching problems
• Multicriteria scheduling
• Title not available (Why is that?)
• Single-Machine Scheduling to Minimize a Function of Two or Three Maximum Cost Criteria
• 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
• Bicriteria scheduling of minimizing maximum lateness and makespan on a serial-batching machine

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
• Bounded serial-batching scheduling for minimizing maximum lateness and makespan
• Bicriteria scheduling on a batching machine to minimize 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)