Scheduling linear deteriorating jobs with rejection on a single machine

DOI10.1016/j.ejor.2007.11.047zbMath1179.90132OpenAlexW2059434334MaRDI QIDQ953419

Yushao Cheng, Shijie Sun

Publication date: 20 November 2008

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2007.11.047

zbMATH Keywords

schedulingdynamic programmingdeteriorating jobsrejection

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items

Scheduling with release times and rejection on two parallel machines ⋮ New approximation algorithms for machine scheduling with rejection on single and parallel machine ⋮ SCHEDULING DETERIORATING JOBS ON A SINGLE MACHINE WITH RELEASE TIMES AND REJECTION ⋮ Parallel-machine scheduling with release dates and rejection ⋮ Due date assignment and single machine scheduling with deteriorating jobs to minimize the weighted number of tardy jobs ⋮ An improved heuristic for parallel machine scheduling with rejection ⋮ A tardiness-augmented approximation scheme for rejection-allowed multiprocessor rescheduling ⋮ Single machine problem with multi-rate-modifying activities under a time-dependent deterioration ⋮ Approximation algorithms for parallel machine scheduling with linear deterioration ⋮ A survey on offline scheduling with rejection ⋮ Online scheduling with deterioration and unexpected processor breakdown ⋮ Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices ⋮ Penalty cost constrained identical parallel machine scheduling problem ⋮ Parallel-batch scheduling with deterioration and rejection on a single machine ⋮ Approximation algorithms for precedence-constrained identical machine scheduling with rejection ⋮ An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration ⋮ A bicriteria approach to scheduling a single machine with job rejection and positional penalties ⋮ Optimal algorithms for online single machine scheduling with deteriorating jobs ⋮ Single-machine scheduling and due date assignment with rejection and position-dependent processing times ⋮ Scheduling on parallel identical machines with job-rejection and position-dependent processing times ⋮ Online scheduling on a single machine with rejection under an agreeable condition to minimize the total completion time plus the total rejection cost ⋮ Multi-machine scheduling with interval constrained position-dependent processing times ⋮ Scheduling simple linear deteriorating jobs with rejection ⋮ Scheduling a bounded parallel-batching machine with incompatible job families and rejection ⋮ Non-permutation flow shop scheduling with order acceptance and weighted tardiness ⋮ Order acceptance and scheduling with consideration of service level ⋮ Batch scheduling with proportional-linear deterioration and outsourcing ⋮ TWO-MACHINE FLOW SHOP SCHEDULING WITH INDIVIDUAL OPERATION'S REJECTION ⋮ Scheduling with job-rejection and position-dependent processing times on proportionate flowshops ⋮ Single-machine scheduling under the job rejection constraint ⋮ Order acceptance and scheduling with machine availability constraints ⋮ Two-machine flow-shop scheduling with rejection ⋮ Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan ⋮ An efficient optimal solution to the coil sequencing problem in electro-galvanizing line ⋮ Parallel-machine scheduling with deteriorating jobs and rejection ⋮ Minimizing the makespan on a single parallel batching machine ⋮ Minmax scheduling and due-window assignment with position-dependent processing times and job rejection ⋮ Applying ``peeling onion approach for competitive analysis in online scheduling with rejection ⋮ Bounded single-machine parallel-batch scheduling with release dates and rejection ⋮ A review of four decades of time-dependent scheduling: main results, new topics, and open problems ⋮ A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration ⋮ Single machine scheduling with release dates and rejection ⋮ Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejection ⋮ Two-agent scheduling with rejection on a single machine ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing total completion time in a two-machine flow shop with deteriorating jobs
• Scheduling jobs under simple linear deterioration
• Single machine scheduling with start time dependent processing times: Some solvable cases
• A concise survey of scheduling with time-dependent processing times
• On-line uniform machine scheduling with rejection
• Minimizing the total weighted completion time of deteriorating jobs
• On-line scheduling of unit time jobs with rejection: Minimizing the total completion time
• Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem
• Scheduling with time dependent processing times: Review and extensions
• Scheduling Deteriorating Jobs on a Single Processor
• V-Shaped Policies for Scheduling Deteriorating Jobs
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• NP-hard cases in scheduling deteriorating jobs on dedicated machines
• Due-date assignment and single machine scheduling with deteriorating jobs
• Flow shop scheduling problems with deteriorating jobs under dominating machines
• Algorithms and Data Structures
• Minimizing maximum lateness under linear deterioration
• Single machine scheduling with step-deteriorating processing times
• Preemptive multiprocessor scheduling with rejection