nach oben

Journal of Scheduling

Erschienen in:

15.12.2017

A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems

verfasst von: Arthur Kramer, Anand Subramanian

Erschienen in: Journal of Scheduling | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This work proposes a unified heuristic algorithm for a large class of earliness–tardiness (E–T) scheduling problems. We consider single/parallel machine E–T problems that may or may not consider some additional features such as idle time, setup times and release dates. In addition, we also consider those problems whose objective is to minimize either the total (average) weighted completion time or the total (average) weighted flow time, which arise as particular cases when the due dates of all jobs are either set to zero or to their associated release dates, respectively. The developed local search-based metaheuristic framework is quite simple, but at the same time relies on sophisticated procedures for efficiently performing local search according to the characteristics of the problem. We present efficient move evaluation approaches for some parallel machine problems that generalize the existing ones for single machine problems. The algorithm was tested in thousands of instances of several E–T problems and particular cases. The results obtained show that our unified heuristic is capable of producing high-quality solutions when compared to the best ones available in the literature that were obtained by specific methods. Moreover, we provide an extensive annotated bibliography on the problems related to those considered in this work, where we not only indicate the approach(es) used in each publication, but we also point out the characteristics of the problem(s) considered. Beyond that, we classify the existing methods in different categories so as to have a better idea of the popularity of each type of solution procedure.

Vorheriger Artikel Inductive -independent graphs and c-colorable subgraphs in scheduling: a review

Nächster Artikel No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Akyol, D., & Bayhan, G. (2008). Multi-machine earliness and tardiness scheduling problem: An interconnected neural network approach. The International Journal of Advanced Manufacturing Technology, 37(5–6), 576–588.

Amorim, R. (2013). Um estudo sobre formulações matemáticas e estratégias algorítmicas para problemas de escalonamento em máquinas paralelas com penalidades de antecipação e atraso. Master’s thesis, Programa de Pós-Graduação em Informática, Instituto de Computação, Universidade Federal do Amazonas, Manaus, AM, Brazil (in Portuguese).

Amorim, R., Dias, B., de Freitas, R., & Uchoa, E. (2013). A hybrid genetic algorithm with local search approach for e/t scheduling problems on identical parallel machines. In: Proceedings of the 15th annual conference companion on genetic and evolutionary computation, ACM, New York, NY, USA, GECCO ’13 Companion, pp. 63–64.

Anghinolfi, D., & Paolucci, M. (2007). Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach. Computers & Operations Research, 34(11), 3471–3490.

Anghinolfi, D., & Paolucci, M. (2008). A new ant colony optimization approach for the single machine total weighted tardiness scheduling problem. International Journal of Operations Research, 5, 44–60.

Anghinolfi, D., & Paolucci, M. (2009). A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 193(1), 73–85.

Armentano, V. A., & de França Filho, M. F. (2007). Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach. European Journal of Operational Research, 183(1), 100–114.

Arroyo, J. E. C., Nunes, G. V. P., & Kamke, E. H. (2009). Iterative local search heuristic for the single machine scheduling problem with sequence dependent setup times and due dates. In G. Yu, M. Köppen, S. M. Chen, & X. Niu (Eds.), HIS (1) (pp. 505–510). Washington: IEEE Computer Society.

Avella, P., Boccia, M., & D’Auria, B. (2005). Near-optimal solutions of large-scale single-machine scheduling problems. INFORMS Journal on Computing, 17(2), 183–191.

Azizoglu, M., & Kirca, O. (1998). Tardiness minimization on parallel machines. International Journal of Production Economics, 55(2), 163–168.

Azizoglu, M., & Kirca, O. (1999). On the minimization of total weighted flow time with identical and uniform parallel machines. European Journal of Operational Research, 113(1), 91–100.

Baker, K. R., & Scudder, G. D. (1990). Sequencing with earliness and tardiness penalties: A review. Operations Research, 38(1), 22–36.

Balakrishnan, N., Kanet, J. J., & Sridharan, V. (1999). Early/tardy scheduling with sequence dependent setups on uniform parallel machines. Computers & Operations Research, 26(2), 127–141.

Bank, J., & Werner, F. (2001). Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties. Mathematical and Computer Modelling, 33(4–5), 363–383.

Baptiste, P., Jouglet, A., & Savourey, D. (2008). Lower bounds for parallel machine scheduling problems. International Journal of Operational Research, 3(6), 643–664.

Belouadah, H., & Potts, C. (1994). Scheduling identical parallel machines to minimize total weighted completion time. Discrete Applied Mathematics, 48(3), 201–218.

Belouadah, H., Posner, M., & Potts, C. (1992). Scheduling with release dates on a single machine to minimize total weighted completion time. Discrete Applied Mathematics, 36(3), 213–231.

Bigras, L. P., Gamache, M., & Savard, G. (2008). The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times. Discrete Optimization, 5(4), 685–699.

Bilge, Ü., Kıraç, F., Kurtulan, M., & Pekgün, P. (2004). A tabu search algorithm for parallel machine total tardiness problem. Computers & Operations Research, 31(3), 397–414.

Biskup, D., & Feldmann, M. (2001). Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates. Computers & Operations Research, 28(8), 787–801.

Biskup, D., Herrmann, J., & Gupta, J. N. (2008). Scheduling identical parallel machines to minimize total tardiness. International Journal of Production Economics, 115(1), 134–142.

Bozejko, W. (2010). Parallel path relinking method for the single machine total weighted tardiness problem with sequence-dependent setups. Journal of Intelligent Manufacturing, 21(6), 777–785.

Bülbül, K., & Şen, H. (2017). An exact extended formulation for the unrelated parallel machine total weighted completion time problem. Journal of Scheduling, 20(4), 373–389.

Bülbül, K., Kaminsky, P., & Yano, C. (2007). Preemption in single machine earliness/tardiness scheduling. Journal of Scheduling, 10, 271–292.

Chekuri, C., & Khanna, S. (2004). Approximation algorithms for minimizing average weighted completion time. In: J. Y.-T. Leung (Ed.), Handbook of scheduling: Algorithms, models, and performance analysis (pp. 11.1–11.30). Boca Raton, FL: CRC Press, Inc.

Chen, Z. L., & Powell, W. B. (1999). Solving parallel machine scheduling problems by column generation. INFORMS Journal on Computing, 11(1), 78–94.

Chu, C. (1992a). A branch-and-bound algorithm to minimize total flow time with unequal release dates. Naval Research Logistics, 39(6), 859–875.

Chu, C. (1992b). A branch-and-bound algorithm to minimize total tardiness with different release dates. Naval Research Logistics (NRL), 39(2), 265–283.

Cicirello, V. A. (2006). Non-wrapping order crossover: An order preserving crossover operator that respects absolute position. In: Proceedings of the genetic and evolutionary computation conference (pp. 1125–1131), ACM Press.

Cicirello, V. A., & Smith, S. F. (2005). Enhancing stochastic search performance by value-biased randomization of heuristics. Journal of Heuristics, 11, 5–34.

Congram, R. K., Potts, C. N., & van de Velde, S. L. (2002). An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS Journal on Computing, 14(1), 52–67.

Cordeau, J. F., & Maischberger, M. (2012). A parallel iterated tabu search heuristic for vehicle routing problems. Computers & Operations Research, 39(9), 2033–2050.

Cordeau, J. F., Laporte, G., & Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52, 928–936.

Della Croce, F. (1995). Generalized pairwise interchanges and machine scheduling. European Journal of Operational Research, 83(2), 310–319. (EURO Summer Institute Combinatorial Optimization).

Della Croce, F., Garaix, T., & Grosso, A. (2012). Iterated local search and very large neighborhoods for the parallel-machines total tardiness problem. Computers & Operations Research, 39(6), 1213–1217. (Special Issue on Scheduling in Manufacturing Systems).

Deng, G., & Gu, X. (2014). An iterated greedy algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. International Journal of Systems Science, 45(3), 351–362.

Derigs, U., & Vogel, U. (2014). Experience with a framework for developing heuristics for solving rich vehicle routing problems. Journal of Heuristics, 20(1), 75–106.

Dyer, M. E., & Wolsey, L. A. (1990). Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics, 26(2–3), 255–270.

Eom, D. H., Shin, H. J., Kwun, I. H., Shim, J. K., & Kim, S. S. (2002). Scheduling jobs on parallel machines with sequence-dependent family set-up times. The International Journal of Advanced Manufacturing Technology, 19(12), 926–932.

Epstein, L., Levin, A., & van Stee, R. (2013). A unified approach to truthful scheduling on related machines. In: S. Khanna (Ed.), Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6–8, 2013, SIAM, pp. 1243–1252.

Ergun, Ö., & Orlin, J. B. (2006). Fast neighborhood search for the single machine total weighted tardiness problem. Operations Research Letters, 34(1), 41–45.

Esteve, B., Aubijoux, C., Chartier, A., & T’kindt, V. (2006). A recovering beam search algorithm for the single machine just-in-time scheduling problem. European Journal of Operational Research, 172(3), 798–813.

Feldmann, M., & Biskup, D. (2003). Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches. Computers & Industrial Engineering, 44(2), 307–323.

Feng, G., & Lau, H. (2008). Efficient algorithms for machine scheduling problems with earliness and tardiness penalties. Annals of Operations Research, 159(1), 83–95.

Feo, T. A., & Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2), 109–133.

França, P. M., Mendes, A., & Moscato, P. (2001). A memetic algorithm for the total tardiness single machine scheduling problem. European Journal of Operational Research, 132(1), 224–242.

Gagné, C., Price, W. L., & Gravel, M. (2002). Comparing an aco algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times. The Journal of the Operational Research Society, 53(8), 895–906.

Gagné, C., Gravel, M., & Price, W. L. (2005). Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems. Journal of the Operational Research Society, 56(6), 687–698.

Garey, M. R., Tarjan, R. E., & Wilfong, G. T. (1988). One-processor scheduling with symmetric earliness and tardiness penalties. Mathematics of Operations Research, 13(2), 330–348.

Geiger, M. J. (2010). On heuristic search for the single machine total weighted tardiness problem—Some theoretical insights and their empirical verification. European Journal of Operational Research, 207(3), 1235–1243.

Graham, R., Lawler, E., Lenstra, J., & Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. In: P. L. Hammer, E. J. Johnson, & B. Korte (Eds.), Discrete optimization II. Proceedings of the advanced research institute on discrete optimization and systems applications of the systems science panel of NATO and of the discrete optimization symposium co-sponsored by IBM Canada and SIAM Banff, Aha. and Vancouver. Annals of discrete mathematics (Vol. 5, pp. 287–326). Amsterdam: Elsevier.

Grosso, A., Croce, F. D., & Tadei, R. (2004). An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem. Operations Research Letters, 32(1), 68–72.

Guinet, A. (1995). Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria. Journal of Intelligent Manufacturing, 6(2), 95–103.

Guo, Q., & Tang, L. (2015). An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times. Applied Soft Computing, 29(C), 184–195.

Guo, Y., Lim, A., Rodrigues, B., & Yu, S. (2004). Minimizing total flow time in single machine environment with release time: An experimental analysis. Computers & Industrial Engineering, 47(2–3), 123–140.

Gupta, S. R., & Smith, J. S. (2006). Algorithms for single machine total tardiness scheduling with sequence dependent setups. European Journal of Operational Research, 175(2), 722–739.

Hendel, Y., & Sourd, F. (2006). Efficient neighborhood search for the one-machine earliness–tardiness scheduling problem. European Journal of Operational Research, 173(1), 108–119.

Hendel, Y., & Sourd, F. (2007). An improved earliness–tardiness timing algorithm. Computers & Operations Research, 34(10), 2931–2938.

Ibaraki, T., Imahori, S., Kubo, M., Masuda, T., Uno, T., & Yagiura, M. (2005). Effective local search algorithms for routing and scheduling problems with general time-window constraints. Transportation Science, 39(2), 206–232.

Ibaraki, T., Imahori, S., Nonobe, K., Sobue, K., Uno, T., & Yagiura, M. (2008). An iterated local search algorithm for the vehicle routing problem with convex time penalty functions. Discrete Applied Mathematics, 156(11), 2050–2069.

Jouglet, A., & Savourey, D. (2011). Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates. Computers & Operations Research, 38(9), 1259–1266.

Józefowska, J. (2007). Just-in-time scheduling: Models and algorithms for computer and manufacturing systems., International series in operations research & management science Berlin: Springer.

Kedad-Sidhoum, S., & Sourd, F. (2010). Fast neighborhood search for the single machine earliness-tardiness scheduling problem. Computers & Operations Research, 37(8), 1464–1471. (Operations Research and Data Mining in Biological Systems).

Kedad-Sidhoum, S., Solis, Y. R., & Sourd, F. (2008). Lower bounds for the earliness–tardiness scheduling problem on parallel machines with distinct due dates. European Journal of Operational Research, 189(3), 1305–1316.

Kellerer, H., Tautenhahn, T., & Woeginger, G. J. (1996). Approximability and nonapproximability results for minimizing total flow time on a single machine. In: Proceedings of the twenty-eighth annual ACM symposium on theory of computing, ACM, New York, NY, USA, STOC ’96, pp. 418–426.

Kim, S. I., Choi, H. S., & Lee, D. H. (2006). Tabu search heuristics for parallel machine scheduling with sequence-dependent setup and ready times. In M. Gavrilova, O. Gervasi, V. Kumar, C. Tan, D. Taniar, A. Laganá, Y. Mun, & H. Choo (Eds.), Computational science and its applications—ICCSA 2006. Lecture notes in computer science (Vol. 3982, pp. 728–737). Berlin: Springer.

Kirlik, G., & Oğuz, C. (2012). A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine. Computers & Operations Research, 39(7), 1506–1520.

Koulamas, C. (1997). Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem. Naval Research Logistics (NRL), 44(1), 109–125.

Kumar, V. S. A., Marathe, M. V., Parthasarathy, S., & Srinivasan, A. (2009). A unified approach to scheduling on unrelated parallel machines. Joural of the ACM, 56(5), 28:1–28:31.

Lauff, V., & Werner, F. (2004). Scheduling with common due date, earliness and tardiness penalties for multimachine problems: A survey. Mathematical and Computer Modelling, 40(5–6), 637–655.

Lawler, E. L. (1977). A ”pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. In P. L. Hammer, B. K. EL Johnson, & G. Nemhauser (Eds.), Studies in integer programming (Annals of discrete mathematics) (Vol. 1, pp. 331–342). Amsterdam: Elsevier.

Lee, J. H., Yu, J. M., & Lee, D. H. (2013). A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: Minimizing total tardiness. The International Journal of Advanced Manufacturing Technology, 69(9–12), 2081–2089.

Lee, Y. H., & Pinedo, M. (1997). Scheduling jobs on parallel machines with sequence-dependent setup times. European Journal of Operational Research, 100(3), 464–474.

Lee, Y. H., Bhaskaran, K., & Pinedo, M. (1997). A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Transactions, 29(1), 45–52.

Lenstra, J., Kan, A. R., & Brucker, P. (1977). Complexity of machine scheduling problems. In P. L. Hammer, B. K. EL Johnson, & G. Nemhauser (Eds.), Studies in integer programming (Annals of discrete mathematics) (Vol. 1, pp. 343–362). Amsterdam: Elsevier.

Leonardi, S., & Raz, D. (2007). Approximating total flow time on parallel machines. Journal of Computer and System Sciences, 73(6), 875–891.

Leyvand, Y., Shabtay, D., & Steiner, G. (2010). A unified approach for scheduling with convex resource consumption functions using positional penalties. European Journal of Operational Research, 206(2), 301–312.

Li, G. (1997). Single machine earliness and tardiness scheduling. European Journal of Operational Research, 96(3), 546–558.

Li, K., & Yang, S. (2009). Non-identical parallel-machine scheduling research with minimizing total weighted completion times: Models, relaxations and algorithms. Applied Mathematical Modelling, 33(4), 2145–2158.

Li, K., Leung, J. T., & Cheng, B. Y. (2014). An agent-based intelligent algorithm for uniform machine scheduling to minimize total completion time. Applied Soft Computing, 25, 277–284.

Liao, C. J., & Cheng, C. C. (2007). A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date. Computers & Industrial Engineering, 52(4), 404–413.

Liao, C. J., & Juan, H. C. (2007). An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups. Computers & Operations Research, 34(7), 1899–1909.

Liao, C. J., Tsou, H. H., & Huang, K. L. (2012). Neighborhood search procedures for single machine tardiness scheduling with sequence-dependent setups. Theoretical Computer Science, 434, 45–52.

Liaw, C. F., Lin, Y. K., Cheng, C. Y., & Chen, M. (2003). Scheduling unrelated parallel machines to minimize total weighted tardiness. Computers & Operations Research, 30(12), 1777–1789.

Lin, S. W., & Ying, K. C. (2007). Solving single-machine total weighted tardiness problems with sequence-dependent setup times by meta-heuristics. The International Journal of Advanced Manufacturing Technology, 34(11–12), 1183–1190.

Lin, Y. K. (2013). Fast LP models and algorithms for identical jobs on uniform parallel machines. Applied Mathematical Modelling, 37(5), 3436–3448.

Lin, Y. K., & Hsieh, F. Y. (2014). Unrelated parallel machine scheduling with setup times and ready times. International Journal of Production Research, 52(4), 1200–1214.

Logendran, R., McDonell, B., & Smucker, B. (2007). Scheduling unrelated parallel machines with sequence-dependent setups. Computers & Operations Research, 34(11), 3420–3438.

Lourenço, H. R., Martin, O. C., & Stützle, T. (2002). Iterated Local Search. In: F. W. Glover, & G. A. Kochenberger (Eds.), Handbook of metaheuristics (pp. 321–353). Norwell, MA: Kluwer Academic Publishers.

Mandahawi, N., Al-Shihabi, S., & Altarazi, S. (2011). A max-min ant system to minimize total tardiness on a single machine with sequence dependet setup times implementing a limited budget local search. International Journal of Research & Reviews in Applied Sciences, 6, 30–40.

Martinelli, R., Poggi, M., & Subramanian, A. (2013). Improved bounds for large scale capacitated arc routing problem. Computers & Operations Research, 40(8), 2145–2160.

Mason, S. J., Jin, S., & Jampani, J. (2005). A moving block heuristic for minimizing earliness and tardiness on a single machine with unrestrictive common due dates. Journal of Manufacturing Systems, 24(4), 328–338.

Mason, S. J., Jin, S., & Jampani, J. (2009). A moving block heuristic to minimise earliness and tardiness costs on parallel machines. International Journal of Production Research, 47(19), 5377–5390.

M’Hallah, R. (2007). Minimizing total earliness and tardiness on a single machine using a hybrid heuristic. Computers & Operations Research, 34(10), 3126–3142.

M’Hallah, R., & Al-Khamis, T. (2012). Minimising total weighted earliness and tardiness on parallel machines using a hybrid heuristic. International Journal of Production Research, 50(10), 2639–2664.

Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097–1100.

Nessah, R., Yalaoui, F., & Chu, C. (2008). A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates. Computers & Operations Research, 35(4), 1176–1190.

Nogueira, J. P. C. M., Arroyo, J. E. C., Villadiego, H. M. M., & Gonçalves, L. B. (2014). Hybrid GRASP heuristics to solve an unrelated parallel machine scheduling problem with earliness and tardiness penalties. Electronic Notes in Theoretical Computer Science, 302, 53 – 72. Proceedings of the XXXIX Latin American Computing Conference (CLEI 2013).

Omar, M. K., & Teo, S. C. (2006). Minimizing the sum of earliness/tardiness in identical parallel machines schedule with incompatible job families: An improved MIP approach. Applied Mathematics and Computation, 181(2), 1008–1017.

Pan, Y., & Shi, L. (2008). New hybrid optimization algorithms for machine scheduling problems. IEEE Transactions on Automation Science and Engineering, 5(2), 337–348.

Penna, P., Subramanian, A., & Ochi, L. (2013). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 19(2), 201–232.

Pereira-Lopes, M. J., & Valério de Carvalho, J. M. (2007). A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times. European Journal of Operational Research, 176(3), 1508–1527.

Pessoa, A., Uchoa, E., de Aragão, M., & Rodrigues, R. (2010). Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems. Mathematical Programming Computation, 2(3–4), 259–290.

Pfund, M., Fowler, J. W., Gadkari, A., & Chen, Y. (2008). Scheduling jobs on parallel machines with setup times and ready times. Computers & Industrial Engineering, 54(4), 764–782.

Pisinger, D., & Røpke, S. (2007). A general heuristic for vehicle routing problems. Computers & Operations Research, 34(8), 2403–2435.

Polyakovskiy, S., & M’Hallah, R. (2014). A multi-agent system for the weighted earliness tardiness parallel machine problem. Computers & Operations Research, 44, 115–136.

Potts, C. N., & Van Wassenhove, L. N. (1991). Single machine tardiness sequencing heuristics. IIE Transactions, 23(4), 346–354.

Radhakrishnan, S., & Ventura, J. A. (2000). Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times. International Journal of Production Research, 38(10), 2233–2252.

Raja, K., Selladurai, V., Saravanan, R., & Arumugam, C. (2008). Earliness–tardiness scheduling on uniform parallel machines using simulated annealing and fuzzy logic approach. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 222(2), 333–346.

Raman, N., Rachamadugu, R. V., & Talbot, F. (1989). Real-time scheduling of an automated manufacturing center. European Journal of Operational Research, 40(2), 222–242.

Ratli, M., Benmansour, R., Macedo, R., Hanafi, S., & Wilbaut, C. (2013). Mathematical programming and heuristics for scheduling problems with early and tardy penalties (pp. 183–223). Hoboken: Wiley.

Rios-Solis, Y., & Sourd, F. (2008). Exponential neighborhood search for a parallel machine scheduling problem. Computers & Operations Research, 35(5), 1697–1712. (Part Special Issue: Algorithms and Computational Methods in Feasibility and Infeasibility).

Rodrigues, R., Pessoa, A., Uchoa, E., & de Aragão, M. P. (2008). Heuristic algorithm for the parallel machine total weighted tardiness scheduling problem. Relatório de Pesquisa em Engenharia de Produçao, 8(10), 1–11.

Ronconi, D. A. P., & Kawamura, M. A. S. (2010). The single machine earliness and tardiness scheduling problem: Lower bounds and a branch-and-bound algorithm. Computational & Applied Mathematics, 29, 107–124.

Røpke, S., & Pisinger, D. (2006). A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 171(3), 750–775.

Rubin, P. A., & Ragatz, G. L. (1995). Scheduling in a sequence dependent setup environment with genetic search. Computers & Operations Research, 22(1), 85–99. (Genetic Algorithms).

Schaller, J. E. (2014). Minimizing total tardiness for scheduling identical parallel machines with family setups. Computers & Industrial Engineering, 72, 274–281.

Selim Akturk, M., & Ozdemir, D. (2000). An exact approach to minimizing total weighted tardiness with release dates. IIE Transactions, 32(11), 1091–1101.

Şen, H., & Bülbül, K. (2015). A strong preemptive relaxation for weighted tardiness and earliness/tardiness problems on unrelated parallel machines. INFORMS Journal on Computing, 27(1), 135–150.

Shim, S. O., & Kim, Y. D. (2007a). Minimizing total tardiness in an unrelated parallel-machine scheduling problem. Journal of the Operational Research Sosciety, 58(3), 346–354.

Shim, S. O., & Kim, Y. D. (2007b). Scheduling on parallel identical machines to minimize total tardiness. European Journal of Operational Research, 177(1), 135–146.

Silva, M. M., Subramanian, A., Vidal, T., & Ochi, L. S. (2012). A simple and effective metaheuristic for the minimum latency problem. European Journal of Operational Research, 221(3), 513–520.

Sioud, A., Gravel, M., & Gagné, C. (2012). A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times. Computers & Operations Research, 39(10), 2415–2424.

Sivrikaya-Şerifoğlu, F., & Ulusoy, G. (1999). Parallel machine scheduling with earliness and tardiness penalties. Computers & Operations Research, 26(8), 773–787.

Sourd, F. (2005). Earliness-tardiness scheduling with setup considerations. Computers & Operations Research, 32(7), 1849–1865.

Sourd, F. (2006). Dynasearch for the earliness–tardiness scheduling problem with release dates and setup constraints. Operations Research Letters, 34(5), 591–598.

Sourd, F. (2009). New exact algorithms for one-machine earliness–tardiness scheduling. INFORMS Journal on Computing, 21(1), 167–175.

Sourd, F., & Kedad-Sidhoum, S. (2003). The one-machine problem with earliness and tardiness penalties. Journal of Scheduling, 6(6), 533–549.

Sourd, F., & Kedad-Sidhoum, S. (2008). A faster branch-and-bound algorithm for the earliness–tardiness scheduling problem. Journal of Scheduling, 11(1), 49–58.

Subramanian, A. (2012). Heuristic, exact and hybrid approaches for vehicle routing problems. PhD thesis, Universidade Federal Fluminense, Niterói, Brazil.

Subramanian, A., & Battarra, M. (2013). An iterated local search algorithm for the travelling salesman problem with pickups and deliveries. Journal of the Operational Research Society, 64(3), 402–409.

Subramanian, A., & Farias, K. (2017). Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times. Computers & Operations Research, 79, 190–206.

Subramanian, A., Drummond, L., Bentes, C., Ochi, L., & Farias, R. (2010). A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 37(11), 1899–1911. (Metaheuristics for Logistics and Vehicle Routing).

Subramanian, A., Uchoa, E., & Ochi, L. S. (2013). A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research, 40(10), 2519–2531.

Subramanian, A., Battarra, M., & Potts, C. N. (2014). An iterated local search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times. International Journal of Production Research, 52(9), 2729–2742.

Sun, H., & Wang, G. (2003). Parallel machine earliness and tardiness scheduling with proportional weights. Computers & Operations Research, 30(5), 801–808.

Tan, K., & Narasimhan, R. (1997). Minimizing tardiness on a single processor with sequence-dependent setup times: A simulated annealing approach. Omega, 25(6), 619–634.

Tanaka, S. (2012). An exact algorithm for the single-machine earliness–tardiness scheduling problem. In R. Z. Ríos-Mercado & Y. A. Ríos-Solís (Eds.), Just-in-time systems, Springer optimization and its applications (pp. 21–40). New York: Springer.

Tanaka, S., & Araki, M. (2008). A branch-and-bound algorithm with lagrangian relaxation to minimize total tardiness on identical parallel machines. International Journal of Production Economics, 113(1), 446–458.

Tanaka, S., & Araki, M. (2013a). An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. Computers & Operations Research, 40(1), 344–352.

Tanaka, S., & Araki, M. (2013b). An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. Computers & Operations Research, 40(1), 344–352.

Tanaka, S., & Fujikuma, S. (2008). An efficient exact algorithm for general single-machine scheduling with machine idle time. In: IEEE international conference on automation science and engineering, 2008. CASE 2008, pp 371–376.

Tanaka, S., & Fujikuma, S. (2012). A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time. Journal of Scheduling, 15(3), 347–361.

Tanaka, S., Fujikuma, S., & Araki, M. (2009). An exact algorithm for single-machine scheduling without machine idle time. Journal of Scheduling, 12(6), 575–593.

Tasgetiren, M. F., Pan, Q. K., & Liang, Y. C. (2009). A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times. Computers & Operations Research, 36(6), 1900–1915.

Tsai, T. (2007). A genetic algorithm for solving the single machine earliness/tardiness problem with distinct due dates and ready times. The International Journal of Advanced Manufacturing Technology, 31(9), 994–1000.

Valente, J. M., & Alves, R. A. (2008). Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups. Computers & Operations Research, 35(7), 2388–2405.

Vallada, E., & Ruiz, R. (2012). Scheduling unrelated parallel machines with sequence dependent setup times and weighted earliness–tardiness minimization. In R. Z. Ríos-Mercado & Y. A. Ríos-Solís (Eds.), Just-in-time systems, Springer optimization and its applications (Vol. 60, pp. 67–90). New York: Springer.

Van den Akker, J., Hurkens, C., & Savelsbergh, M. (2000). Time-indexed formulations for machine scheduling problems: Column generation. INFORMS Journal on Computing, 12(2), 111–124.

Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013). A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers & Operations Research, 40(1), 475–489.

Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2014). A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234(3), 658–673.

Vidal, T., Battarra, M., Subramanian, A., & Erdoǧan, G. (2015a). Hybrid metaheuristics for the clustered vehicle routing problem. Computers & Operations Research, 58, 87–99.

Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2015b). Timing problems and algorithms: Time decisions for sequences of activities. Networks, 65(2), 102–128.

Wan, G., & Yen, B. P. C. (2002). Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties. European Journal of Operational Research, 142(2), 271–281.

Wan, L., & Yuan, J. (2013). Single-machine scheduling to minimize the total earliness and tardiness is strongly np-hard. Operations Research Letters, 41(4), 363–365.

Webster, S. (1992). New bounds for the identical parallel processor weighted flow time problem. Management Science, 38(1), 124–136.

Webster, S. (1995). Weighted flow time bounds for scheduling identical processors. European Journal of Operational Research, 80(1), 103–111.

Webster, S. T. (1993). A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems. European Journal of Operational Research, 70(3), 327–334.

Weng, M. X., Lu, J., & Ren, H. (2001). Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective. International Journal of Production Economics, 70(3), 215–226.

Xi, Y., Jang, J., Friedman, D., & Hou, W. (2015). A tardiness-concerned constructive method for the identical parallel machine scheduling. The International Journal of Advanced Manufacturing Technology, 79(5–8), 851–862.

Xu, H., Lü, Z., & Cheng, T. (2013). Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness. Journal of Scheduling, 17, 271–287.

Xu, H., Lü, Z., Yin, A., Shen, L., & Buscher, U. (2014). A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times. Computers & Operations Research, 50, 47–60.

Yalaoui, F., & Chu, C. (2002). Parallel machine scheduling to minimize total tardiness. International Journal of Production Economics, 76(3), 265–279.

Yalaoui, F., & Chu, C. (2006). New exact method to solve the \(P_m|r_j|\sum C_j\) schedule problem. International Journal of Production Economics, 100(1), 168–179.

Yano, C. A., & Kim, Y. D. (1991). Algorithms for a class of single-machine weighted tardiness and earliness problems. European Journal of Operational Research, 52(2), 167–178.

Ying, K. C., Lin, S. W., & Huang, C. Y. (2009). Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic. Expert Systems with Applications, 36(3, Part 2), 7087–7092.

Yoon, S. H., & Lee, I. S. (2011). New constructive heuristics for the total weighted tardiness problem. Journal of the Operational Research Society, 62(1), 232–237.

Yousefi, M., & Yusuff, R. M. (2013). Minimising earliness and tardiness penalties in single machine scheduling against common due date using imperialist competitive algorithm. International Journal of Production Research, 51(16), 4797–4804.

Zhou, H., Li, Z., & Wu, X. (2007). Scheduling unrelated parallel machine to minimize total weighted tardiness using ant colony optimization. In: 2007 IEEE international conference on automation and logistics, pp 132–136.

Zhu, Z., & Heady, R. B. (2000). Minimizing the sum of earliness/tardiness in multi-machine scheduling: A mixed integer programming approach. Computers & Industrial Engineering, 38(2), 297–305.

Titel: A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems
verfasst von: Arthur Kramer
Anand Subramanian
Publikationsdatum: 15.12.2017
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 1/2019
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-017-0549-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2019

A polynomial-time approximation scheme for the airplane refueling problem

An efficient train scheduling algorithm on a single-track railway system

Scheduling and rescheduling elective patients in operating rooms to minimise the percentage of tardy patients

No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths

The venue management problem: setting staffing levels, shifts and shift schedules at concession stands

Journal of scheduling (2019)