tailieunhanh - Effective heuristics for solving dynamic variant of single processor total tardiness problems

This paper considers the dynamic variant of single processor scheduling problem of minimizing total tardiness. In practice, it occurs when minimizing tardiness penalty. The problem is NP-hard; thus two heuristics were proposed. | Effective heuristics for solving dynamic variant of single processor total tardiness problems Journal of Project Management 3 2018 13 22 Contents lists available at GrowingScience Journal of Project Management homepage Effective heuristics for solving dynamic variant of single processor total tardiness problems Saheed Akandea Ayodeji Emmanuel Oluleyeb and Elkanah Oyetunjic a Department of Mechanical and Mechatronics Engineering Afe Babalola University Ado-Ekiti Nigeria b Department of Industrial and Production Engineering University of Ibadan Nigeria c Department of Mechanical Engineering Lagos State University Nigeria CHRONICLE ABSTRACT Article history This paper considers the dynamic variant of single processor scheduling problem of minimizing Received July 5 2017 total tardiness. In practice it occurs when minimizing tardiness penalty. The problem is NP- Received in revised format Octo- hard thus two heuristics were proposed. The utility of the proposed models was demonstrated ber 10 2017 through computational experiments and comparative analyses against existing solution methods Accepted November 10 2017 Available online and the Branch and Bound BB method. The results show that the proposed models yield effi- November 14 2017 cient solutions and in most cases perform effectively better than the existing heuristics in the Keywords literature. Heuristics Branch and Bound Total Tardiness Efficient solution Effective 2018 Growing Science Ltd. 1. Introduction Scheduling a set of jobs which are to be processed on a single processor to minimize the total tardiness is known as the Single Processor Total Tardiness Problems SPTTP . When the release dates of all the jobs are effectively zero the problem is static. Otherwise it is called the dynamic variant Pinedo 2008 . Effective scheduling of jobs to minimize the total tardiness is very important in manufacturing production and servicing systems where penalty cost is proportional to total .