Four single-machine scheduling problems involving due date determination decisions

详细信息    查看全文

• 作者：Yunqiang Yin ; Min Liu ; T.C.E. Cheng ; Chin-Chia Wu ; Shuenn-Ren Cheng
• 关键词：Scheduling ; Due date assignment ; Past-sequence-dependent delivery time ; Position-dependent learning effect
• 刊名：Information Sciences
• 出版年：2013
• 出版时间：1 December, 2013
• 年：2013
• 卷：251
• 期：Complete
• 页码：164-181
• 全文大小：484 K

文摘

This paper considers single-machine scheduling problems with simultaneous consideration of due date assignment, past-sequence-dependent (p-s-d) delivery times, and position-dependent learning effects. By p-s-d delivery times, we mean that the delivery time of a job is proportional to the job¡¯s waiting time. Specifically, we study four variants of the problem: (i) the variant of total earliness and tardiness with common due date assignment (referred to as TETDC), (ii) the variant of total earliness and weighted number of tardy jobs with CON due date assignment (referred to as TEWNTDC), (iii) the variant of total earliness and weighted number of tardy jobs with slack due date assignment (referred to as TEWNTDS), and (iv) the variant of weighted number of tardy jobs with different due date assignment (referred to as WNTDD). We derive the structural properties of the optimal schedules and show that the variants TETDC, TEWNTDC and TEWNTDS are all polynomially solvable. Although the complexity status of the variant WNTDD is still open, we show that two special cases of it are polynomially solvable.