یک مدل برنامه‏ریزی عدد صحیح مختلط غیرخطی برای بازپرسازی سفارشات و الگوریتم ابتکاری جهت حل آن

نوع مقاله: مقاله پژوهشی

نویسندگان

1 دانشیار عضو هیئت علمی دانشگاه تربیت مدرس

2 دانشجوی کارشناسی ارشد دانشگاه تربیت مدرس

3 استادیار عضو هیئت علمی دانشگاه تربیت مدرس

چکیده

مسائل برنامه‌ریزی تولید عموما به­عنوان مسائل برنامه‌ریزی عدد صحیح مختلط مدلسازی می‌شوند؛ و به علت پیچیدگی محاسباتی بالا و ذاتی این نوع مسائل، از طریق الگوریتم‌های ابتکاری حل می‌شوند. در این مقاله، یک مدل برنامه‌ریزی عدد صحیح مختلط غیرخطی برای برنامه‌ریزی تولید چند محصولی- چند دوره‌ای به­منظور بازپرسازی سفارشات خریدار و کمینه‌سازی هزینه‌های تأمین‌کننده طراحی شده است. در این مدل فرض بر آن است که مقدار سفارش ثابت است و سفارش‌دهی یک‌باره انجام می‌شود. این مدل مطابق با مفروضات شرکت ساپکو که یک تامین‌کننده بزرگ قطعات اتوموبیل در ایران است، و یکی از شرکت‌های همکار آن توسعه یافته است. همچنین، یک الگوریتم ابتکاری کارآمد مبتنی بر جست‌وجوی A* برای حل این مدل ریاضی پیشنهاد شده است. الگوریتم جست‌وجوی پیشنهادی نیازی به یک جواب اولیه ندارد؛ همچنین با اعمال کنترل بر حالت‌های ذخیره شده در لیست آماده شاخه‌زنی می‌تواند بر محدودیت سربار حافظه غلبه نماید. در حقیقت علی‌رغم سادگی این الگوریتم که بر اساس روابط ساده مدیریت موجودی بنا شده است، قادر است در مقایسه با روش حل دقیق، یک الگوریتم جست‌وجوی حریصانه، و الگوریتم شبیه‌سازی تبرید به عنوان یک الگوریتم فراابتکاری، به صورت کارآمدی جواب‌های بهینه یا نزدیک بهینه حاصل آورد.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

A Mixed Integer Nonlinear Programming Model for Order Replenishment and a Heuristic Algorithm for its Solution

نویسندگان [English]

  • Reza Baradaran kazemzadeh 1
  • zohreh kaheh 2
  • Ellips Masehian 3
1 University of Tarbiat Modares
2 University of Tarbiat Modares
3 University of Tarbiat Modares
چکیده [English]

Production planning problems are generally modeled as mixed integer programming problems; and solved through heuristic algorithms, because of their innate high computational complexity. In this paper, a mixed integer nonlinear programming (MINLP) model is designed for multi-item, multi-period production planning to replenish orders of the buyer and minimizing the supplier’s costs. It is supposed that the order quantity is constant, and ordering occurs at once. This model has been developed according to the realistic assumptions of SAPCO Company, which is a major supplier of automotive parts in Iran, and one of its partner companies. In addition, an efficient heuristic algorithm based on A* search has been proposed to solve this mathematical model. The proposed search algorithm does not need an initial solution; also, it can overcome the memory overhead through bounding the stored states in its open-list. Actually, in spite of the simplicity of the proposed algorithm, which is established based on the simple inventory management equations; it is able to generate efficiently optimal or near-optimal solutions in comparison with an exact solution method, a greedy search algorithm, and simulated annealing algorithm as a metaheuristic algorithm.

کلیدواژه‌ها [English]

  • Order replenishment
  • Mixed integer nonlinear programming
  • Heuristic algorithm
  • A* search