A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs
From MaRDI portal
Publication:2438422
DOI10.3934/JIMO.2014.10.1071zbMATH Open1292.90330arXiv1301.7134OpenAlexW2963206272MaRDI QIDQ2438422FDOQ2438422
Authors: Peng Guo, Wenming Cheng, Yi Wang 
Publication date: 11 March 2014
Published in: Journal of Industrial and Management Optimization (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1301.7134
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
heuristictotal tardinesssingle-machine schedulingstep-deteriorationgeneral variable neighborhood search
Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Mixed integer programming (90C11)
Cites Work
- Scheduling. Theory, algorithms, and systems.
- Variable neighborhood search
- Variable neighbourhood search: methods and applications
- Minimizing Total Tardiness on One Machine is NP-Hard
- A general variable neighborhood search for solving the uncapacitated single allocation \(p\)-hub median problem
- Scheduling Deteriorating Jobs on a Single Processor
- Minimizing maximum lateness under linear deterioration
- A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine
- Variable neighborhood decomposition search
- The single-machine total tardiness scheduling problem: review and extensions
- Single machine scheduling with start time dependent processing times: Some solvable cases
- A concise survey of scheduling with time-dependent processing times
- Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs
- 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
- Variable neighborhood search for parallel machines scheduling problem with step deteriorating jobs
- Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times
- 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
- Single machine scheduling with step-deteriorating processing times
- A memetic algorithm for minimizing the total weighted completion time on a single machine under step-deterioration
- Parallel-machine scheduling of simple linear deteriorating jobs
- Scheduling linear deteriorating jobs to minimize the number of tardy jobs
- Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem
- V-Shaped Policies for Scheduling Deteriorating Jobs
- An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan
- Scheduling jobs with piecewise linear decreasing processing times
- Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times
- New heuristics for solving the economic lot scheduling problem with reworks
- Scheduling deteriorating jobs to minimize makespan
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
Uses Software
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)
