Scheduling problem with multi-purpose parallel machines

详细信息    查看全文

• 作者：Rosiane de Freitas Rodrigues ; Mitre Costa Dourado ; Jayme Luiz Szwarcfiter
• 关键词：Algorithms ; Scheduling theory ; Unit penalty function ; Unit time jobs
• 刊名：Discrete Applied Mathematics
• 出版年：19 February, 2014
• 年：2014
• 卷：164
• 期：part_P1
• 页码：313-319
• 全文大小：451 K

文摘

We consider a multi-purpose identical parallel machine scheduling problem, in which jobs should be executed on some machine belonging to a given subset of the set of machines. The problem is , where there are independent unit-time jobs, time window constraints, identical parallel multi-purpose machines, and the objective is the minimization of the total weighted number of tardy jobs. The best previous complexity for this problem is , employing network flow techniques. We develop an algorithm that handles successive nesting of on-time jobs more efficiently, with overall time complexity.