Improved algorithms for two single machine scheduling problems

DOI10.1016/J.TCS.2006.04.014zbMATH Open1110.68014OpenAlexW2611886938MaRDI QIDQ860871FDOQ860871

Authors: Huikun Gu, Yong He, Wei-ya Zhong 

Publication date: 9 January 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.04.014

Recommendations

• Algorithmic Applications in Management
• Heuristics for the two-machine scheduling problem with a single server
• Algorithms for some maximization scheduling problems on a single machine
• An improved algorithm for scheduling two identical machines with batch delivery consideration
• Improved algorithms for single machine scheduling with release dates and rejections
• An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time
• An improved approximation algorithm for single machine scheduling with job delivery
• An approximation algorithm for two-machine scheduling with an availability constraint
• scientific article; zbMATH DE number 5630095
• scientific article

zbMATH Keywords

schedulingworst-case ratiodelivery

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Cites Work

• Machine scheduling with job delivery coordination
• Fast Approximation Algorithms for Knapsack Problems
• Title not available (Why is that?)
• Single machine flow-time scheduling with a single breakdown
• An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
• Single machine flow-time scheduling with scheduled maintenance
• A simple proof of the inequality \(\text{FFD}(L)\leq {11 \over 9} \text{OPT}(L)+1\), \(\forall L\) for the FFD bin-packing algorithm
• Title not available (Why is that?)

Cited In (35)

• Two parallel machines problem with job delivery coordination and availability constraint
• Scheduling with cardinality dependent unavailability periods
• Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates
• Unrelated parallel machine scheduling with eligibility constraints and delivery times to minimize total weighted tardiness
• Two-stage scheduling on identical machines with assignable delivery times to minimize the maximum delivery completion time
• Two-machine flowshop scheduling with intermediate transportation under job physical space consideration
• On the machine scheduling problem with job delivery coordination
• Scheduling with job delivery coordination on single machine
• Algorithmic Applications in Management
• A new heuristic algorithm for the machine scheduling problem with job delivery coordination
• Approximation algorithms for the single-machine scheduling with a period of maintenance
• Coordinated scheduling of the outsourcing, in-house production and distribution operations
• Integrated scheduling of production and delivery on a single machine with availability constraint
• Single Machine Scheduling with an Availability Constraint and Rejection
• Single machine scheduling with job delivery to multiple customers
• Semi-online scheduling on a single machine with unexpected breakdown
• Minimizing total weighted completion time with an unexpected machine unavailable interval
• Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval
• Improved approaches to minimize the makespan on single-machine scheduling with periodic preventive maintenance activities
• Supply chain scheduling problem in the hospital with periodic working time on a single machine
• Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval
• The Coordination of Two Parallel Machines Scheduling and Batch Deliveries
• Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time
• Short‐term scheduling with machine calibration
• Minimizing total weighted late work on a single-machine with non-availability intervals
• Minimizing total completion time on a single machine with a flexible maintenance activity
• Single bounded parallel-batch machine scheduling with an unavailability constraint and job delivery
• Two parallel machines scheduling with two-vehicle job delivery to minimize makespan
• Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags
• Online and semi-online scheduling to minimize makespan on single machine with an availability constraint
• Single-machine scheduling with machine unavailability periods and resource dependent processing times
• Preemptive scheduling on identical machines with delivery coordination to minimize the maximum delivery completion time
• Machine scheduling with a maintenance interval and job delivery coordination
• Machine scheduling with a maintenance interval and job delivery coordination
• Parallel machine scheduling with job delivery coordination

This page was built for publication: Improved algorithms for two single machine scheduling problems

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