Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints
Pages 169 - 185
Abstract
In this paper we investigate the problem of scheduling a set of jobs on a single-machine. The jobs are classified in families and setup times are required between the processing of two jobs of different families. Each job requires a certain amount of a common resource that is supplied through upstream processes. The total resource consumed must not exceed the resource supply up. Therefore, jobs may have to wait and the machine has to be idle due to an insufficient availability of the resource. To minimize the total tardiness, simple and effective iterated greedy (IG) heuristics are proposed. Different neighborhood operators are used in the local search phase. To choose the right neighborhood operators, we propose an adaptive selecting strategy. The heuristics are tested over an extensive computational experience on benchmark of instances from the literature and instances randomly generated in this work. Experimental results and statistical tests show that the proposed heuristics are able to obtain high-quality solutions within reasonable computational effort, and they outperform the state-of-the-art heuristic.
References
[1]
Herr O and Goel AMinimising total tardiness for a single machine scheduling problem with family setups and resource constraintsEur. J. Oper. Res.20162481123-13533935031346.90351
[2]
Du J and Leung JY-TMinimizing total tardiness on one machine is np-hardMath. Oper. Res.1990153483-49510642130714.90052
[3]
Koulamas CThe single-machine total tardiness scheduling problem: review and extensionsEur. J. Oper. Res.201020211-725564171175.90174
[4]
Sen T, Sulek JM, and Dileepan P Static scheduling research to minimize weighted and unweighted tardiness: a state-of-the-art survey Int. J. Prod. Econ. 2003 83 1 1-12
[5]
Emmons HOne-machine sequencing to minimize certain functions of job tardinessOper. Res.1969174701-7152438260176.50005
[6]
Lawler ELA “pseudopolynomial” algorithm for sequencing jobs to minimize total tardinessAnn. Discrete Math.19771331-3424564200353.68071
[7]
Allahverdi A, Ng C, Cheng TE, and Kovalyov MYA survey of scheduling problems with setup times or costsEur. J. Oper. Res.20081873985-103223783261137.90474
[8]
Potts CN and Kovalyov MYScheduling with batching: a reviewEur. J. Oper. Res.20001202228-24917857090953.90028
[9]
Gupta SR and Smith JSAlgorithms for single machine total tardiness scheduling with sequence dependent setupsEur. J. Oper. Res.20061752722-7391142.90399
[10]
Liao C-J and Juan H-CAn ant colony optimization for single-machine tardiness scheduling with sequence-dependent setupsComput. Oper. Res.20073471899-19091112.90030
[11]
Lin S and Ying K A hybrid approach for single-machine tardiness problems with sequence-dependent setup times J. Oper. Res. Soc. 2008 59 8 1109-1119
[12]
Ying K-C, Lin S-W, and Huang C-Y Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic Expert Syst. Appl. 2009 36 3 7087-7092
[13]
Sioud A, Gravel M, and Gagné CA hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup timesComput. Oper. Res.201239102415-242428853571251.90189
[14]
Bigras L-P, Gamache M, and Savard GThe time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup timesDiscret. Optim.200854685-69924508761152.90425
[15]
Tanaka S and Araki MAn exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup timesComput. Oper. Res.2013401344-35229791171349.90402
[16]
Subramanian A, Battarra M, and Potts CN An iterated local search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times Int. J. Prod. Res. 2014 52 9 2729-2742
[17]
Gupta JN and Chantaravarapan SSingle machine group scheduling with family setups to minimize total tardinessInt. J. Prod. Res.20084661707-17221160.90398
[18]
Schaller J Scheduling on a single machine with family setups to minimize total tardiness Int. J. Prod. Econ. 2007 105 2 329-344
[19]
Potts CN and Van Wassenhove LNIntegrating scheduling with batching and lot-sizing: a review of algorithms and complexityJ. Oper. Res. Soc.1992435395-4060756.90050
[20]
Schaller JE and Gupta JNSingle machine scheduling with family setups to minimize total earliness and tardinessEur. J. Oper. Res.200818731050-106823783291137.90516
[21]
Vilar Jacob, V., Arroyo, J.E.C.: Ils heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness. J. Appl. Math. 2016 (2016)
[22]
Peng Y, Han Y, Xiao Y, and Ullah SHeuristics for single machine scheduling problem with family setup timesInt. J. Comput. Sci. Math.201782166-1743650825
[23]
Briskorn D, Choi B-C, Lee K, Leung J, and Pinedo MComplexity of single machine scheduling subject to nonnegative inventory constraintsEur. J. Oper. Res.20102072605-61926705941205.90115
[24]
Briskorn D, Jaehn F, and Pesch EExact algorithms for inventory constrained scheduling on a single machineJ. Sched.2013161105-11530302071297.90065
[25]
Fanjul-Peyro L and Ruiz RIterated greedy local search methods for unrelated parallel machine schedulingEur. J. Oper. Res.2010207155-6926594201205.90121
[26]
Ruiz R and Stützle TA simple and effective iterated greedy algorithm for the permutation flowshop scheduling problemEur. J. Oper. Res.200717732033-20491110.90042
[27]
Ruiz, R., Pan, Q.-K., Naderi, B.: Iterated Greedy methods for the distributed permutation flowshop scheduling problem. Omega (2018)
[28]
Rodriguez FJ, Lozano M, Blum C, and García-Martínez CAn iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problemComput. Oper. Res.20134071829-184130493461348.90305
[29]
Kang Q, He H, and Wei J An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems J. Parallel Distrib. Comput. 2013 73 8 1106-1115
[30]
Zhou S, Liu M, Chen H, and Li X An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes Int. J. Prod. Econ. 2016 179 1-11
Index Terms
- Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints
Index terms have been assigned to the content through auto-classification.
Recommendations
An Effective Heuristic for a Single-Machine Scheduling Problem with Family Setups and Resource Constraints
Learning and Intelligent OptimizationAbstractThis paper presents a simple and effective iterated greedy heuristic to minimize the total tardiness in a single-machine scheduling problem. In this problem the jobs are classified in families and setup times are required between the processing of ...
Single machine scheduling problems with deteriorating jobs
This paper considers the single machine scheduling problems with deteriorating jobs, i.e. jobs whose processing times are a decreasing linear function of their starting time. It is assumed that jobs have the different basic processing time and same ...
A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints
In this paper, we consider two problems about the preemptive scheduling of a set of jobs with release times on a single machine. In the first problem, each job has a deadline. The objective is to find a feasible schedule which minimizes the total ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© Springer Nature Switzerland AG 2019.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 01 March 2020
Author Tags
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 30 Dec 2024