首页 | 本学科首页   官方微博 | 高级检索  
     


Single machine scheduling with interfering job sets
Affiliation:1. Faculty of Engineering and Sciences, Universidad Adolfo Ibáñez, Av. Pedro Hurtado 750, Office A-215, Viña del Mar, Chile;2. Department of Industrial Engineering, Universidad de Talca, Merced 437, Universidad de Talca, Curicó, Chile
Abstract:We consider two single machine bicriteria scheduling problems in which jobs belong to either of two different disjoint sets, each set having its own performance measure. The problem has been referred to as interfering job sets in the scheduling literature and also been called multi-agent scheduling where each agent's objective function is to be minimized. In the first problem (P1) we look at minimizing total completion time and number of tardy jobs for the two sets of jobs and present a forward SPT-EDD heuristic that attempts to generate the set of non-dominated solutions. The complexity of this specific problem is NP-hard; however some pseudo-polynomial algorithms have been suggested by earlier researchers and they have been used to compare the results from the proposed heuristic. In the second problem (P2) we look at minimizing total weighted completion time and maximum lateness. This is an established NP-hard problem for which we propose a forward WSPT-EDD heuristic that attempts to generate the set of supported points and compare our solution quality with MIP formulations. For both of these problems, we assume that all jobs are available at time zero and the jobs are not allowed to be preempted.
Keywords:Interfering job sets  Single machine scheduling  Heuristic approaches  Mixed integer programming
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号