Hybrid metaheuristic approaches for the single machine total stepwise tardiness problem with release dates

作     者：Chaurasia, Sachchida Nand Sundar, Shyam Singh, Alok 

作者机构：Univ Hyderabad Sch Comp & Informat Sci Hyderabad 500046 Andhra Prades India Natl Inst Technol Raipur Dept Comp Applicat GE Rd Raipur 492010 Madhya Pradesh India 

出 版 物：《OPERATIONAL RESEARCH》 (运筹学)

年 卷 期：2017年第17卷第1期

页      面：275-295页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主　　题：Single machine total stepwise tardiness problem Artificial bee colony algorithm Genetic algorithm Heuristic Release dates Scheduling 

摘      要：This paper presents two hybrid metaheuristic approaches, viz. a hybrid genetic algorithm and a hybrid artificial bee colony algorithm for a single machine scheduling problem where tardiness cost of a job increases stepwise with various due dates and the objective is to minimize the total tardiness cost. This kind of tardiness cost occurs in several real life scenarios particularly in transportation. Two versions of the scheduling problem are considered. In the first version, all jobs are assumed to be available for processing at the beginning, whereas in the latter version jobs have release dates. For both versions, we have employed a local search to further improve the solutions obtained through our metaheuristic approaches. To the best of our knowledge, our approaches are the first metaheuristic approaches for the latter version of the problem. For the first version, we have compared our approaches with the state-of-the-art approaches available in the literature. Computational results show the superiority of our approaches over previous approaches in terms of solution quality and running time both. For the latter version, hybrid artificial bee colony algorithm based approach outperformed the hybrid genetic algorithm based approach in terms of solution quality and running time both.