দুটি মেশিনে কাজ শিডিউলিং#

এই সমস্যাটি হলো দুটি মেশিনে $n$ টি কাজের জন্য সর্বোত্তম শিডিউল খুঁজে বের করা। প্রতিটি আইটেমকে প্রথমে প্রথম মেশিনে এবং তারপর দ্বিতীয় মেশিনে প্রসেস করতে হবে। $i$-তম কাজ প্রথম মেশিনে $a_i$ সময় এবং দ্বিতীয় মেশিনে $b_i$ সময় নেয়। প্রতিটি মেশিন একবারে কেবল একটি কাজ প্রসেস করতে পারে।

আমরা কাজগুলোর সর্বোত্তম ক্রম খুঁজতে চাই, যাতে চূড়ান্ত প্রসেসিং সময় সর্বনিম্ন সম্ভব হয়।

এখানে আলোচিত সমাধানটিকে জনসনের নিয়ম বলা হয় (S. M. Johnson-এর নামে নামকরণ)।

লক্ষণীয় যে, দুটির বেশি মেশিন থাকলে সমস্যাটি NP-complete হয়ে যায়।

অ্যালগরিদমের গঠন#

প্রথমে লক্ষ্য করুন, আমরা ধরে নিতে পারি যে প্রথম এবং দ্বিতীয় মেশিনের জন্য কাজের ক্রম একই হতে হবে। প্রকৃতপক্ষে, যেহেতু দ্বিতীয় মেশিনের জন্য কাজগুলো প্রথম মেশিনে প্রসেস করার পরই উপলব্ধ হয়, এবং যদি দ্বিতীয় মেশিনে একাধিক কাজ উপলব্ধ থাকে, তাহলে প্রসেসিং সময় তাদের $b_i$-এর যোগফলের সমান হবে, তাদের ক্রম যাই হোক না কেন। তাই কাজগুলো দ্বিতীয় মেশিনে প্রথম মেশিনে পাঠানোর একই ক্রমে পাঠানোই সুবিধাজনক।

কাজগুলোর ক্রম বিবেচনা করুন, যা তাদের ইনপুট ক্রম $1, 2, \dots, n$-এর সাথে মিলে যায়।

$x_i$ দ্বারা $i$ প্রসেস করার ঠিক আগে দ্বিতীয় মেশিনের অলস সময় চিহ্নিত করি। আমাদের লক্ষ্য মোট অলস সময় ন্যূনতম করা:

$$F(x) = \sum x_i ~ \rightarrow \min$$

প্রথম কাজের জন্য $x_1 = a_1$। দ্বিতীয় কাজের জন্য, যেহেতু এটি $a_1 + a_2$ সময়ে মেশিনে পাঠানো হয়, এবং দ্বিতীয় মেশিন $x_1 + b_1$ সময়ে মুক্ত হয়, আমরা পাই $x_2 = \max\left((a_1 + a_2) - (x_1 + b_1), 0\right)$। সাধারণভাবে আমরা সমীকরণ পাই:

$$x_k = \max\left(\sum_{i=1}^k a_i - \sum_{i=1}^{k-1} b_i - \sum_{i=1}^{k-1} x_i, 0 \right)$$

এখন আমরা মোট অলস সময় $F(x)$ গণনা করতে পারি। দাবি করা হয় যে এটি নিচের আকারের

$$F(x) = \max_{k=1 \dots n} K_i,$$

যেখানে

$$K_i = \sum_{i=1}^k a_i - \sum_{i=1}^{k-1} b_i.$$

এটি ইন্ডাকশন দিয়ে সহজেই যাচাই করা যায়।

এখন আমরা পারমুটেশন পদ্ধতি ব্যবহার করি: আমরা দুটি প্রতিবেশী কাজ $j$ এবং $j+1$ বিনিময় করব এবং দেখব এটি কিভাবে মোট অলস সময় পরিবর্তন করে।

$K_i$-এর রাশির আকার থেকে স্পষ্ট যে কেবল $K_j$ এবং $K_{j+1}$ পরিবর্তন হয়, আমরা তাদের নতুন মানকে $K_j'$ এবং $K_{j+1}'$ দিয়ে চিহ্নিত করি।

যদি $j$ এবং $j+1$ কাজের এই পরিবর্তন মোট অলস সময় বাড়ায়, তাহলে নিশ্চয়ই:

$$\max(K_j, K_{j+1}) \le \max(K_j', K_{j+1}')$$

(দুটি কাজ বিনিময়ের কোনো প্রভাব নাও থাকতে পারে। উপরের শর্তটি কেবল একটি যথেষ্ট শর্ত, প্রয়োজনীয় শর্ত নয়।)

অসমতার উভয় পক্ষ থেকে $\sum_{i=1}^{j+1} a_i - \sum_{i=1}^{j-1} b_i$ বাদ দিলে পাই:

$$\max(-a_{j+1}, -b_j) \le \max(-b_{j+1}, -a_j)$$

এবং ঋণাত্মক চিহ্ন দূর করলে:

$$\min(a_j, b_{j+1}) \le \min(b_j, a_{j+1})$$

এভাবে আমরা একটি কম্প্যারেটর পেলাম: এই কম্প্যারেটর অনুসারে কাজগুলো সাজালে, আমরা কাজগুলোর সর্বোত্তম ক্রম পাই, যেখানে চূড়ান্ত সময়ের উন্নতি করে কোনো দুটি কাজ বিনিময় করা যায় না।

তবে আপনি কম্প্যারেটরকে ভিন্ন দৃষ্টিকোণ থেকে দেখলে সাজানো আরও সরলীকরণ করতে পারেন। কম্প্যারেটরটি নিম্নভাবে ব্যাখ্যা করা যায়: যদি আমাদের চারটি সময় $(a_j, a_{j+1}, b_j, b_{j+1})$ থাকে, এবং তাদের মধ্যে সর্বনিম্নটি প্রথম মেশিনের সাথে সম্পর্কিত একটি সময় হয়, তাহলে সংশ্লিষ্ট কাজটি প্রথমে করা উচিত। যদি সর্বনিম্ন সময় দ্বিতীয় মেশিনের হয়, তাহলে এটি পরে করা উচিত। এভাবে আমরা কাজগুলোকে $\min(a_i, b_i)$ অনুসারে সাজাতে পারি, এবং যদি বর্তমান কাজের প্রথম মেশিনে প্রসেসিং সময় দ্বিতীয় মেশিনে প্রসেসিং সময়ের চেয়ে কম হয়, তাহলে এই কাজটি অবশিষ্ট সমস্ত কাজের আগে করতে হবে, অন্যথায় সমস্ত অবশিষ্ট কাজের পরে।

যেভাবেই হোক, দেখা যায় যে জনসনের নিয়ম অনুযায়ী আমরা সাজানোর মাধ্যমে সমস্যা সমাধান করতে পারি, এবং ফলে সময় কমপ্লেক্সিটি হয় $O(n \log n)$।

ইমপ্লিমেন্টেশন#

এখানে আমরা বর্ণিত অ্যালগরিদমের দ্বিতীয় ভিন্নরূপটি ইমপ্লিমেন্ট করি।

struct Job {
    int a, b, idx;

    bool operator<(Job o) const {
        return min(a, b) < min(o.a, o.b);
    }
};

vector<Job> johnsons_rule(vector<Job> jobs) {
    sort(jobs.begin(), jobs.end());
    vector<Job> a, b;
    for (Job j : jobs) {
        if (j.a < j.b)
            a.push_back(j);
        else
            b.push_back(j);
    }
    a.insert(a.end(), b.rbegin(), b.rend());
    return a;
}

pair<int, int> finish_times(vector<Job> const& jobs) {
    int t1 = 0, t2 = 0;
    for (Job j : jobs) {
        t1 += j.a;
        t2 = max(t2, t1) + j.b;
    }
    return make_pair(t1, t2);
}

প্রতিটি কাজের সমস্ত তথ্য struct-এ সংরক্ষিত। প্রথম ফাংশনটি সমস্ত কাজ সাজায় এবং সর্বোত্তম শিডিউল গণনা করে। দ্বিতীয় ফাংশনটি একটি শিডিউল দেওয়া থাকলে উভয় মেশিনের শেষ হওয়ার সময় গণনা করে।