A Tabu Search Algorithm for an Excavator Scheduling Problem

Abstract

Global sector prompts the construction firms to give a priority to time and cost factors. Thus, scheduling of the jobs is focal important to achieve cost and time objectives. Scheduling problems have gained a great importance in recent years in the construction sector. We have examined a single machine scheduling problem for an excavator used in the construction sector. There are some jobs in which each job has a normal processing time, a due date, earliness penalty and tardiness penalty. This paper presents a meta-heuristic optimization algorithm named Tabu Search (TS) to minimize the total cost and provides how it can be used to solve a wide variety of single machine scheduling problems. Computational results demonstrates that the proposed approach is a good tool for these problems.

Keywords

• Tabu search
• single machine scheduling problem
• excavator
• construction sector

A Tabu Search Algorithm for an Excavator Scheduling Problem

Abstract

Global sector prompts the construction firms to give a priority to time and cost factors. Thus, scheduling of the jobs is focal important to achieve cost and time objectives. Scheduling problems have gained a great importance in recent years in the construction sector. We have examined a single machine scheduling problem for an excavator used in the construction sector. There are some jobs in which each job has a normal processing time, a due date, earliness penalty and tardiness penalty. This paper presents a meta-heuristic optimization algorithm named Tabu Search (TS) to minimize the total cost and provides how it can be used to solve a wide variety of single machine scheduling problems. Computational results demonstrates that the proposed approach is a good tool for these problems.

Keywords

• Tabu search
• single machine scheduling problem
• excavator
• construction sector

References

1. [1] M. Ben-daya and M. Al-Fawzan, “An efficient Tabu search algorithm for the single machine mean tardiness problem”. Production Planning and Control, vol. 8, no, 7, 1997.
2. [2] K. Xu, Z. Feng, and K. Jun, “A tabu-search algorithm for scheduling jobs with controllable processing times on a single machine to meet due-dates”, Computers & Operations Research, vol. 37, no. 11, pp. 1924–1938, 2010.
3. [3] V. Ateş, and N. Barışçı, “Short-term load forecasting model using flower pollination algorithm”, International Scientific and Vocational Studies Journal, vol. 1, no. 1, pp. 22-29.2017.
4. [4] İ. B. Koç, A. Al Janadi, and V. Ateş, “Interlock optimization of an accelerator using genetic algorithm”, International Scientific and Vocational Studies Journal, vol. 1, no. 1, pp. 30-41, 2017.
5. [5] C. Oguz, F. Salman, and Z. Yalçın, “Order acceptance and scheduling decisions in make-to-order systems”, International Journal of Production Economics, vol. 125, pp. 200–211, 2010.
6. [6] M. Laguna, J. W. Barnes, and F. Glover, “Tabu search methods for a single machine scheduling problem”, Journal of Intelligent Manufacturing, vol. 2, pp. 63–74, 1991.
7. [7] J. S. Chen, “Using integer programming to solve the machine scheduling problem with a flexible maintenance activity”, Journal of Statistics and Management Systems, vol. 9, no. 1, pp. 87–104, 2006.
8. [8] J. S. Chen, “Optimization models for the machine scheduling problem with a single flexible maintenance activity”, Engineering Optimization, vol. 38, no. 1, 53–71, 2006.

9. [9] O. Hinder, and A. J. Mason, “A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness”, European Journal of Operational Research, vol. 262, no. 2, pp. 411-423, 2017.
10. [10] A. Ghodratnama, M. Rabbani, R. Tavakkoli-Moghaddam, and A. Baboli, “Solving a single-machine scheduling problem with maintenance, job deterioration and learning effect by simulated annealing”, Journal of Manufacturing Systems, vol 29, no. 1, pp. 1-9, 2010.
11. [11]V. Kayvanfar, I. Mahdavi, G.M. Komaki, “Single machine scheduling with controllable processing times to minimize total tardiness and earliness”, Computers & Industrial Engineering, vol. 65, no. 1, pp. 166-175, 2013.
12. [12] I. Adiri, J. Bruno, E. Frostig, A. H. G. Rinnooy Kan, “Single machine flow time scheduling with a single breakdown”, Acta Informatica, vol. 26, no. 7, pp. 679–696, 1989.
13. [13] F. Jin, J. N. Gupta, S. Song, C. Wu, “Single machine scheduling with sequence-dependent family setups to minimize maximum lateness”, Journal of the Operational Research Society, vol. 61, no. 7, pp. 1181-1189, 2010.
14. [14] A. Yurtkuran and E. Emel, “A discrete artificial bee colony algorithm for single machine scheduling problems”, International Journal of Production Research, vol. 54, no. 22, pp. 6860-6878, 2016.
15. [15] Y. Suppiah, and M. K. Omar, “A hybrid tabu search for batching and sequencing decisions in a single machine environment”, Computers & Industrial Engineering, vol. 78, pp. 135-147, 2014.
16. [16] M. T. Almeida, and M. Centeno, “A composite heuristic for the single machine early/tardy job scheduling problem”, Computers & Operations Research, vol. 25, no. 7-8, pp. 625–635, 1998.
17. [17] J. M. S Valente, and R. A. F. S. Alves, “Heuristics for The Single Machine Scheduling Problem with Quadratic Earliness and Tardiness Penalties”, Computers & Operational Research, vol. 35, pp. 3696–3713, 2008.
18. [18] F. Della Croce, and V. T'kindt, “A recovering beam search algorithm for the one-machine dynamic total completion time scheduling problem”, Journal of the Operational Research Society, vol. 53, no. 11, pp. 1275-1280, 2002.
19. [19] A. Jouglet, D. Savourey, J. Carlier, and P. Baptiste, “Dominance-based heuristics for one-machine total cost scheduling problems”, European Journal of Operational Research, vol. 184, no. 3, pp. 879-899, 2008.
20. [20] M. Vila, and J. Pereira, “Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties”, Computers & Operations Research, vol. 40, no. 7, pp. 1819-1828, 2013.
21. [21] F. Della Croce, F. Salassa, and V. T'kindt, “ A hybrid heuristic approach for single machine scheduling with release times”, Computers & Operations Research, vol. 45, pp. 7-11, 2014.
22. [22] R. M’Hallah, and A. Alhajraf, “Ant colony systems for the single-machine total weighted earliness tardiness scheduling problem”, Journal of Scheduling, vol. 19, no. 2, pp. 191-205, 2016.
23. [23] B. Yang, J. Geunes, and W. J. O'Brien, “A heuristic approach for minimizing weighted tardiness and overtime costs in single resource scheduling”, Computers & Operations Research, vol. 31, no. 8, pp. 1273-1301, 2004.