Algorithms/job sequencing

لنفترض أن لدينا مصفوفة تضمّ عددًا من الأعمال التي يرتبط كلٌّ منها بموعد للإنجاز وبمردود مالي يمكن الحصول عليه عند إتمام العمل قبل الموعد المحدد. ولنفترض أنّ كل عمل يستغرق وحدة واحدة من الزمن، وبهذا يكون أقل موعد مسموح به لإنجاز العمل هو 1. كيف يمكن زيادة المردود المالي الكلي إن كان بالإمكان القيام بعمل واحد فقط في نفس الوقت؟

مثال:

المدخلات: أربعة أعمال مع مواعيد الإنجاز والأرباح التالية:

JobID  Deadline  Profit
  a      4        20 
  b      1        10
  c      1        40
  d      1        30

المخرجات: يمكن أداء الأعمال التالية للحصول على أعلى مردود مالي

c, a

المدخلات: خمسة أعمال مع مواعيد الإنجاز والأرباح التالية

JobID   Deadline  Profit
  a       2        100
  b       1        19
  c       2        27
  d       1        25
  e       3        15

المخرجات: يمكن أداء الأعمال التالية للحصول على أعلى مردود مالي

c, a, e

خطوات الخوارمية

يتلخّص الحلّ البسيط لهذه المسألة في توليد جميع المجاميع الفرعية لمجموعة الأعمال المعطاة ثم التحقق في كل مجموعة فرعية على حدة من إمكانية أداء الأعمال الموجودة فيها، ومتابعة أقصى قيمة ممكنة للأرباح في جميع المجاميع الفرعية التي تحقق الشروط أعلاه. يبلغ التعقيد الزمني لهذه الطريقة مقدارًا أسّيًا.

يمكن حلّ هذه المسألة باتباع أسلوب الخوارميات الجشعة وفقًا للخطوات التالية:

1. ترتّب جميع الأعمال ترتيبًا تنازليًا بالاعتماد على الأرباح.
2. تهيئة النتيجة لتكون أوّل عمل في ضمن الأعمال المرتّبة.
3. تنفيذ ما يلي لما تبقى من الأعمال:
   • إن كان العمل الحالي ملائمًا في التسلسل الناتج دون تفويت موعد إنجاز العمل، يُضاف ذلك العمل إلى النتيجة الحالية، وإلا تتجاهله الخوارزمية.

تنفيذ الخوارزمية

• C++‎:

#include<iostream> 
#include<algorithm> 
using namespace std; 

// بنية لتمثيل العمل
struct Job 
{ 
char id;	 // معرف العمل
int dead; // موعد إنجاز العمل 
int profit; // المردود المالي من إنجاز العمل في موعد الإنجاز أو قبله
}; 

// تستخدم هذه الدالة لترتيب جميع الأعمال وفق المردود المالي
bool comparison(Job a, Job b) 
{ 
	return (a.profit > b.profit); 
} 

// تعيد الدالة أقلّ عدد مطلوب من المنصات
void printJobScheduling(Job arr[], int n) 
{ 
	// ترتيب جميع الأعمال تنازليًا وفق المردود المالي
	sort(arr, arr+n, comparison); 

	int result[n]; // تستخدم هذه المصفوفة لتخزين النتيجة (تسلسل الأعمال)
	bool slot[n]; // تستخدم هذه المصفوفة لمتابعة الأوقات الخالية من العمل 

	// تهيئة جميع المواقع في المصفوفة لتكون مواقع خالية من العمل
	for (int i=0; i<n; i++) 
		slot[i] = false; 

	// المرور على جميع الأعمال المعطاة
	for (int i=0; i<n; i++) 
	{ 
	// إيجاد مكان شاغر لهذا العمل (لاحظ أنّنا نبدأ من أقل موقع ممكن)
	for (int j=min(n, arr[i].dead)-1; j>=0; j--) 
	{ 
		// عُثر على الموقع الشاغر
		if (slot[j]==false) 
		{ 
			result[j] = i; // إضافة هذا العمل إلى النتيجة
			slot[j] = true; // جعل هذا الموقع مشغولًا
			break; 
		} 
	} 
	} 

	// طباعة النتيجة
	for (int i=0; i<n; i++) 
	if (slot[i]) 
		cout << arr[result[i]].id << " "; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	Job arr[] = { {'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27}, 
				{'d', 1, 25}, {'e', 3, 15}}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	cout << "Following is maximum profit sequence of jobsn"; 
	printJobScheduling(arr, n); 
	return 0; 
}

• بايثون:

# تجدول هذه الدالة الأعمال وتأخذ معاملين
# هما مصفوفة الأعمال وعدد الأعمال التي ستجدولها
def printJobScheduling(arr, t): 

	# طول المصفوفة
	n = len(arr) 
    
    # ترتيب جميع الأعمال تنازليًا وفق المردود المالي
	for i in range(n): 
		for j in range(n - 1 - i): 
			if arr[j][2] < arr[j + 1][2]: 
				arr[j], arr[j + 1] = arr[j + 1], arr[j] 

	# تستخدم هذه القائمة لمتابعة الأوقات الخالية من العمل
	result = [False] * t 
    
    # تستخدم هذه القائمة لتخزين النتيجة (تسلسل الأعمال)
	job = ['-1'] * t 

	# المرور على جميع الأعمال
	for i in range(len(arr)): 

		# إيجاد وقع شاغر لهذا العمل
		# لاحظ أنّنا نبدأ من أقل موقع ممكن
		for j in range(min(t - 1, arr[i][1] - 1), -1, -1): 
			
			# عُثر على موقع شاغر
			if result[j] is False: 
				result[j] = True
				job[j] = arr[i][0] 
				break

	# طباعة التسلسل
	print(job) 

# اختبار الدوال السابقة 
arr = [['a', 2, 100], # Job Array 
	['b', 1, 19], 
	['c', 2, 27], 
	['d', 1, 25], 
	['e', 3, 15]] 


print("Following is maximum profit sequence of jobs") 
printJobScheduling(arr, 3) # Function Call

تعطي الشيفرات السابقة المخرجات التالية:

Following is maximum profit sequence of jobs
c a e

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(n^2)‎.

مصادر

• صفحة Job Sequencing Problem في توثيق الخوارزميات في موقع GeeksforGeeks.