অ্যাসাইনমেন্ট সমস্যা কী?

অ্যাসাইনমেন্ট সমস্যা একটি ক্লাসিক কম্বিনেটোরিয়াল অপটিমাইজেশন সমস্যা: কর্মী এবং কাজের একটি সেট দেওয়া হলে, প্রতিটির সাথে একটি সম্পর্কিত খরচ থাকলে, এক-থেকে-এক জোড়া খুঁজে বের করুন যা মোট খরচ কমায়। এটি স্বাভাবিকভাবে সময়সূচী, লজিস্টিকস, সম্পদ বরাদ্দ এবং অপারেশনস রিসার্চে প্রদর্শিত হয় — যেকোনো পরিস্থিতিতে যেখানে আপনাকে দুটি গ্রুপকে সবচেয়ে দক্ষ উপায়ে মেলাতে হবে।

সমস্যাটি হাঙ্গেরিয়ান অ্যালগরিদম দিয়ে সমাধান করা হয় (যাকে মাঙ্কেস অ্যালগরিদমও বলা হয়), একটি দক্ষ পদ্ধতি যা ১৯৫০ এর দশকে বিকশিত হয়েছিল। ব্রুট-ফোর্স পদ্ধতির বিপরীতে যা প্রতিটি পারমিউটেশন মূল্যায়ন করতে হয়, হাঙ্গেরিয়ান অ্যালগরিদম বহুপদ সময়ে সর্বোত্তম সমাধান খুঁজে পায়, যা এটিকে মধ্যম আকারের ম্যাট্রিক্সের জন্যও ব্যবহারিক করে তোলে।

টুল বর্ণনা

একটি খরচ ম্যাট্রিক্স প্রবেশ করুন যা প্রতিটি কর্মীকে প্রতিটি কাজে অ্যাসাইন করতে কত খরচ হয় তা প্রতিনিধিত্ব করে, তারপর সমাধান করুন ক্লিক করুন সর্বোত্তম অ্যাসাইনমেন্ট তাৎক্ষণিকভাবে খুঁজে পেতে। টুলটি হাইলাইট করে কোন কর্মী-কাজ জোড়া মোট খরচ কমায় এবং ফলাফল একটি স্পষ্ট টেবিলে সর্বোত্তম মোট খরচের সাথে প্রদর্শন করে।

উদাহরণ

ইনপুট ম্যাট্রিক্স (৩ কর্মী × ৩ কাজ):

কাজ ১ কাজ ২ কাজ ৩
কর্মী ১ 400 150 400
কর্মী ২ 400 450 600
কর্মী ৩ 300 225 300

সর্বোত্তম অ্যাসাইনমেন্ট:

কর্মী কাজ খরচ
কর্মী ১ কাজ ২ 150
কর্মী ২ কাজ ১ 400
কর্মী ৩ কাজ ৩ 300

মোট খরচ: ৮৫০

বৈশিষ্ট্য

  • সম্পাদনযোগ্য ম্যাট্রিক্স — যেকোনো সেল বা কলাম হেডার ক্লিক করুন কর্মী, কাজ এবং খরচ সরাসরি টেবিলে পুনঃনাম করতে
  • কনফিগারযোগ্য আকার — ২×२ থেকে ৮×८ পর্যন্ত ম্যাট্রিক্স সমর্থন করে
  • তাৎক্ষণিক ফলাফল — হাঙ্গেরিয়ান অ্যালগরিদম ব্রাউজারে চলে কোনো সার্ভার রাউন্ড-ট্রিপ ছাড়াই

এটি কীভাবে কাজ করে

টুলটি অ্যাসাইনমেন্ট সমস্যা সর্বোত্তমভাবে সমাধান করতে মাঙ্কেস (হাঙ্গেরিয়ান) অ্যালগরিদম ব্যবহার করে। এটি আপনার ইনপুট থেকে একটি খরচ ম্যাট্রিক্স তৈরি করে, সারি এবং কলাম হ্রাসের একটি সিরিজ প্রয়োগ করে, এবং পুনরাবৃত্তিমূলকভাবে শূন্যের সর্বাধিক ম্যাচিং খুঁজে পায় যতক্ষণ না একটি সম্পূর্ণ সর্বোত্তম অ্যাসাইনমেন্ট চিহ্নিত করা হয়। সময় জটিলতা হল $O(n^3)$, যেখানে $n$ হল ম্যাট্রিক্স মাত্রা।

অ-বর্গ ম্যাট্রিক্সের জন্য (আরও কর্মী কাজের চেয়ে বা বিপরীতে), অ্যালগরিদম ম্যাট্রিক্সকে শূন্য দিয়ে প্যাড করে যাতে প্রতিটি কর্মী এবং প্রতিটি কাজ মেলানো হয়।

বিকল্প ব্যাখ্যা করা হয়েছে

  • কর্মীর সংখ্যা / সারি — খরচ ম্যাট্রিক্সে কতগুলি সারি প্রদর্শিত হয় তা নিয়ন্ত্রণ করে (२–८)
  • কাজের সংখ্যা / কলাম — খরচ ম্যাট্রিক্সে কতগুলি কলাম প্রদর্শিত হয় তা নিয়ন্ত্রণ করে (२–८)
  • খরচ ম্যাট্রিক্স সেল — একটি নির্দিষ্ট কর্মীকে একটি নির্দিষ্ট কাজে অ্যাসাইন করার খরচ প্রবেশ করুন; যেকোনো সংখ্যাসূচক মান গৃহীত হয়

সীমাবদ্ধতা

  • ম্যাট্রিক্স আকার ८×८ এ সীমাবদ্ধ (६४ সেল)
  • অ্যালগরিদম মোট খরচ কমায়; সর্বাধিক করতে (যেমন, লাভ ম্যাট্রিক্সের জন্য), মান প্রবেশ করার আগে তাদের নেতিবাচক করুন
  • অ-সংখ্যাসূচক সেল মান শূন্য হিসাবে বিবেচিত হয়