A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs
From MaRDI portal
Publication:2438422
Abstract: In this article, we study a single-machine scheduling problem of minimizing the total tardiness for a set of independent jobs. The processing time of a job is modeled as a step function of its starting time and a specific deteriorating date. A mixed integer programming model was applied to the problem and validated. Since the problem is known to be NP-hard, we proposed a heuristic named simple weighted search procedure (SWSP) and a general variable neighborhood search algorithm (GVNS). A perturbation procedure with 3-opt is embedded within the GVNS process in order to explore broader spaces. Extensive numerical experiments are carried out on some randomly generated test instances so as to investigate the performance of the proposed algorithms. By comparing to the results of the CPLEX optimization solver, the heuristic SWSP and the standard variable neighborhood search, it is shown that the proposed GVNS algorithm can provide better solutions within a reasonable running time.
Recommendations
- Variable neighborhood search for parallel machines scheduling problem with step deteriorating jobs
- A population-based variable neighborhood search for the single machine total weighted tardiness problem
- Neighborhood search procedures for single machine tardiness scheduling with sequence-dependent setups
- A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine
- An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem
- Applying variable neighborhood search to the single-machine maximum lateness rescheduling problem
- Variable neighborhood search for the single machine scheduling problem to minimize the total early work
- A variable neighborhood search algorithm for solving the single machine scheduling problem with periodic maintenance
- Analysis of variable neighborhood descent as a local search operator for total weighted tardiness problem on unrelated parallel machines
- Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs
Cites work
- A concise survey of scheduling with time-dependent processing times
- A general variable neighborhood search for solving the uncapacitated single allocation \(p\)-hub median problem
- A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem
- A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times
- A memetic algorithm for minimizing the total weighted completion time on a single machine under step-deterioration
- A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine
- An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan
- Batch scheduling with step-deteriorating processing times to minimize flowtime
- Branch-and-bound and weight-combination search algorithms for the total completion time problem with step-deteriorating jobs
- Makespan minimization in single-machine scheduling with step-deterioration of processing times
- Minimizing Total Tardiness on One Machine is NP-Hard
- Minimizing maximum lateness under linear deterioration
- Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times
- Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem
- Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs
- New heuristics for solving the economic lot scheduling problem with reworks
- Parallel-machine scheduling of simple linear deteriorating jobs
- Scheduling Deteriorating Jobs on a Single Processor
- Scheduling deteriorating jobs to minimize makespan
- Scheduling jobs with piecewise linear decreasing processing times
- Scheduling linear deteriorating jobs to minimize the number of tardy jobs
- Scheduling. Theory, algorithms, and systems.
- Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times
- Single machine scheduling with start time dependent processing times: Some solvable cases
- Single machine scheduling with step-deteriorating processing times
- The single-machine total tardiness scheduling problem: review and extensions
- V-Shaped Policies for Scheduling Deteriorating Jobs
- Variable neighborhood decomposition search
- Variable neighborhood search
- Variable neighborhood search for parallel machines scheduling problem with step deteriorating jobs
- Variable neighbourhood search: methods and applications
Cited in
(12)- Parallel-Machine Scheduling with Step-Deteriorating Jobs to Minimize the Total (Weighted) Completion Time
- Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects
- Nested general variable neighborhood search for the periodic maintenance problem
- Modeling the parallel machine scheduling problem with step deteriorating jobs
- Hybrid differential evolution optimisation for Earth observation satellite scheduling with time-dependent earliness-tardiness penalties
- Algorithms based on VNS for solving the single machine scheduling problem with earliness and tardiness penalties
- A decomposition-based two-stage optimization algorithm for single machine scheduling problems with deteriorating jobs
- A two-agent single-machine scheduling problem with late work criteria
- A population-based variable neighborhood search for the single machine total weighted tardiness problem
- A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine
- Hybridization of harmony search with variable neighborhood search for restrictive single-machine earliness/tardiness problem
- Variable neighborhood search for parallel machines scheduling problem with step deteriorating jobs
This page was built for publication: A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2438422)
