Parallel-machine scheduling with time-dependent and machine availability constraints
Summary: We consider the parallel-machine scheduling problem in which the machines have availability constraints and the processing time of each job is simple linear increasing function of its starting times. For the makespan minimization problem, which is NP-hard in the strong sense, we discuss the Longest Deteriorating Rate algorithm and List Scheduling algorithm; we also provide a lower bound of any optimal schedule. For the total completion time minimization problem, we analyze the strong NP-hardness, and we present a dynamic programming algorithm and a fully polynomial time approximation scheme for the two-machine problem. Furthermore, we extended the dynamic programming algorithm to the total weighted completion time minimization problem.
- Parallel machines scheduling with deteriorating jobs and availability constraints
- Parallel machine scheduling with time dependent processing times
- scientific article; zbMATH DE number 6672186
- Scheduling deteriorating jobs with availability constraints to minimize the makespan
- Parallel-machine scheduling with time dependent processing times
- A concise survey of scheduling with time-dependent processing times
- Approximation algorithms for parallel machine scheduling with linear deterioration
- Complexity and approximability of scheduling resumable proportionally deteriorating jobs
- scientific article; zbMATH DE number 1389747 (Why is no real title available?)
- Machine scheduling with an availability constraint
- Parallel-machine scheduling of simple linear deteriorating jobs
- Scheduling Deteriorating Jobs on a Single Processor
- Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine
- Scheduling linear deteriorating jobs with an availability constraint on a single machine
- Scheduling resumable deteriorating jobs on a single machine with non-availability constraints
- Single-machine scheduling with proportionally deteriorating jobs subject to availability constraints
- Time-dependent scheduling
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times
- Machine scheduling with availability constraints
- Parallel machine scheduling with completion-time-based criteria and sequence-dependent deterioration
- Parallel-machine scheduling with non-simultaneous machine available time
- Optimal parallel machines scheduling with availability constraints
- Formulations, features of solution space, and algorithms for line-pure \textit{seru} system conversion
- Parallel machine scheduling with time dependent processing times
- Two parallel-machine scheduling problems with function constraint
- Parallel machines scheduling with deteriorating jobs and availability constraints
- Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods
- Parallel-machine scheduling with potential disruption and positional-dependent processing times
- scientific article; zbMATH DE number 6672186 (Why is no real title available?)
- Scheduling two parallel machines with machine-dependent availabilities
- scientific article; zbMATH DE number 6453531 (Why is no real title available?)
- Bicriteria scheduling concerned with makespan and total completion time subject to machine availability constraints
- Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints
This page was built for publication: Parallel-machine scheduling with time-dependent and machine availability constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1667046)
