A branch-and-bound algorithm for a single machine sequencing to minimize the total tardiness with arbitrary release dates and position-dependent learning effects

详细信息    查看全文

• 作者：Yunqiang Yin ; Wen-Hung Wu ; Wen-Hsiang Wu ; Chin-Chia Wu
• 关键词：Scheduling ; Single-machine ; Tardiness ; Learning effect
• 刊名：Information Sciences
• 出版年：20 January, 2014
• 年：2014
• 卷：256
• 期：Complete
• 页码：91-108
• 全文大小：962 K

文摘

This study considers an NP-hard problem of minimizing the total tardiness on a single machine with arbitrary release dates and position-dependent learning effects. A mixed-integer programming (MIP ) model is first formulated to find the optimal solution for small-size problem instances. Some new dominance rules are then presented which provide a sufficient condition for finding local optimality. The branch-and-bound (B& B) strategy incorporating with several dominance properties and a lower bound is proposed to derive the optimal solution for medium- to-large-size problem instances, and four marriage-in-honey-bees optimization algorithms (MBO) are developed to derive near-optimal solutions for the problem. To show the effectiveness of the proposed algorithms, 3600 situations with 20 and 25 jobs, are randomly generated for experiments.