کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4635926 1340716 2006 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness
چکیده انگلیسی

This paper addresses the NP-hard problem of scheduling N jobs on a single machine with due dates, sequence-dependent setup times, and no preemption where the objective is to minimize the total tardiness. This problem has previously been treated by Rubin and Ragatz [P.A. Rubin, G.L. Ragatz, Scheduling in a sequence dependent setup environment with generic search, Computers and Operations Research 22 (1) (1995) 85–99], Ragatz [G.L. Ragatz, A branch-and-bound method for minimum tardiness sequencing on a single processor with sequence dependent setup times, in: Proceedings: twenty-fourth annual meeting of the Decision Sciences Institute, 1993, pp. 1375–1377] and Tan et al. [K.C. Tan, R. Narasinmhan, P.A. Rubin, G.L. Ragatz, A comparison of four methods for minimizing total tardiness on a single processor with sequence dependent setup times, Omega 28 (2000) 313–326]. An algorithm based on branch-and-bound permutation schemes is developed including the implementation of lower and upper bounding procedures, and dominance rules. Computational experiments demonstrate the effectiveness of the algorithm. A comparison with Ragatz’s B&B approaches indicates that the algorithm that we describe is competitive and has a certain advantage for larger problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 183, Issue 1, 1 December 2006, Pages 575–588
نویسندگان
, ,