Solution algorithms for the number of tardy jobs minimisation scheduling with a time-dependent learning effect

Abstract

This paper deals with a single-machine scheduling problem with a time-dependent learning effect. The goal is to determine the job sequence that minimise the number of tardy jobs. Two dominance properties, two heuristic algorithms and a lower bound to speed up the search process of the branch-and-bound algorithm are proposed. Computational experiments show that the branch-and-bound algorithm can solve instances up to 18 jobs in a reasonable amount of time, and the proposed heuristic algorithm MFLA performs effectively and efficiently

Keywords:

• sequencing
• scheduling
• single machine
• learning effect
• time-dependent

Acknowledgements

We are grateful to two anonymous referees for their helpful comments on an earlier version of this paper.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by the National Natural Science Foundation of China [grant number 11401115], [grant number 11471012], [grant number 71673220]; and the Science Foundation Research of Department of Education, Shanxi Province [grant number 15JK1475].