A branch and bound algorithm to minimize the sum of maximum earliness and tardiness in single machine

سال انتشار: 1387
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 2,651

فایل این مقاله در 18 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

IIEC06_071

تاریخ نمایه سازی: 8 مهر 1387

چکیده مقاله:

In this paper, we consider the problem of scheduling n jobs on a single machine to minimize the sum of maximum earliness and tardiness. Each job has a processing time and a due date. Since this problem is trying to minimize and diminish the values of earliness, the results and new dominance rules based on pairwise interchanges and a novel property called "Neutrality", a baranch-and bound scheme with beckward approach is proposed. the proposed algorithm is then tested on a set of randomly generated problems of different sizes, varying from 5 to 1000 jobs. Using these approaches, we are able to solve all problems in a reasonable time. Computational results demonstrate the efficiency of our branch and bound algorithm over the existing methods reported in the literature.

نویسندگان

Mehdi Mahnam

Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran

Ghasem Moslehi

Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • Baker, K.R., Introduction to sequencing and scheduling, John Wiley Sons, ...
  • Sidney, J.B., *Optimal singl e-machine scheduling with earliness and tardiness ...
  • Kanet, J.J., *Minimizing the average deviation of job completion times ...
  • Baker, K.R., and Scudder, G.D., «Sequencing with earliness and tardiness ...
  • Hoogeveen, H., ،#Multicriteria scheduling?, European Journal of Operational Research, Vol. ...
  • Hoogeveen, H., and Van de Velde, S.M., ،، Earline ss-tardiness ...
  • Kovalyov, M.Y., and Kubiak, W., ،0A fully polynomial approximati On ...
  • Gordon, V., Proth, J.M., and Chu, C., ،0A survey of ...
  • Kanet, J.J., and Sridharan, V., *Scheduling with inserted idle time: ...
  • Held, M., and Karp, R.M., ،0A dynamic programming approach to ...
  • 1. Abdul-Razaq, T.S., and Potts, C.N., _ programming state-space relaxation ...
  • Azizoglu, M., Kondakci, S., and Kirca, O., ، Bicriteria scheduling ...
  • Sousa, J.P., and Wolsey, L.A., ،A time indexed formulation of ...
  • Li, G., *Single machine earliness and tardiness scheduling?, European Journal ...
  • Liaw, C.F., ،0A branch and bound algorithm for the single ...
  • Valente, J.M.S., and Alves, R.A.F.S., «Improved lower bounds for the ...
  • Ow, P.S., and Morton, E.T., ،The single machine early/tardy problem', ...
  • James, R.J.W., and Buchanan, J.T., ،، Nei ghborhood scheme with ...
  • problem', Naval Research Logistics, Vol. 41, 1994, pp. 33-46. ...
  • Mosheiov, G., ،، Due-date assignment with asymmetric e arline ss-tardiness ...
  • Mosheiov, G., and Oron, A., ،#Minmax scheduling with job-classes and ...
  • algorithm for single machine sequencing to minimize Optimal؛ 28. Amin-Nayeri, ...
  • Tavakko l i-Moghaddam, R., Moslehi, G., Vasei, M., and Azaron, ...
  • Tavakkol i- Moghaddam, R., Moslehi, G., Vasei, M., and Azaron, ...
  • and appro ximation in Optimization؛ 31. Graham, R.E., Lawler, E.L., ...
  • نمایش کامل مراجع