A single-machine scheduling problem with learning effect, deterioration and non-monotonic time-dependent processing times

Abstract

One of the most common objectives in single-machine scheduling problems is the minimisation of total tardiness. Due to the non-deterministic polynomial-time hard nature of this problem, different heuristic and metaheuristic algorithms have been employed to solve it. In this article, an integer programming model with non-monotonic time-dependent job processing times is developed in which deterioration and learning considerations are incorporated simultaneously. A hybrid genetic algorithm-tabu search (GA-TS) approach is employed to solve the problem. Also, to improve the performance of the GA, Taguchi method is used for parameter tuning. Lastly, in an attempt to validate the proposed model, different test problems are generated randomly and solved by both the hybrid GA-TS and an optimisation software, and thereafter a comparison is performed between the results obtained by them. According to the results, the developed approach has potential to yield near-optimum solutions in large-sized problems. To the best of our knowledge, this is the first study that considers non-monotonic time-dependent processing times, deterioration and learning effect simultaneously in a single-machine scheduling problem with the objective of total tardiness minimisation.

Keywords:

• single-machine scheduling
• tardiness
• non-monotonic time dependent processing times
• learning effect
• deteriorating jobs

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This study was supported by a grant from University of Tehran [No. 8106013/1/20]. The authors are grateful for the support provided by the College of Engineering, University of Tehran, Tehran, Iran. This study was also supported by a grant from the Iran National Science Foundation [No. 94002128]. The authors are grateful for the financial support provided by the Iran National Science Foundation.