جدولة المتجر المفتوح

تُعدّ جدولة الورشة المفتوحة ( OSSP ) مسألة تحسين في علوم الحاسوب وبحوث العمليات ، وهي شكلٌ من أشكال جدولة المهام المثلى . في مسألة جدولة المهام العامة _، لدينا n مهمة J1 ، _{J2 ،} ... ، Jn ذات أوقات معالجة متفاوتة، والتي يجب جدولتها على m آلة ذات قدرات معالجة متفاوتة، مع محاولة تقليل زمن الإنجاز الكلي (أي المدة الإجمالية للجدولة حتى انتهاء معالجة جميع المهام). في الشكل المحدد المعروف باسم جدولة الورشة المفتوحة ، تتكون كل مهمة من مجموعة عمليات O1 _، O2 ، _... ، On _التي يجب معالجتها بترتيب عشوائي . دُرست هذه المسألة لأول مرة من قِبل ^{تيوفيلو} ف. غونزاليس وسارتاج ساهني عام 1976. [ ^{1 ]}      

في الترميز القياسي ذي الحقول الثلاثة لمسائل جدولة الوظائف المثلى ، يُرمز إلى متغير الورشة المفتوحة بالحرف O في الحقل الأول. على سبيل المثال، المسألة التي يُرمز إليها بـ " O3|${\displaystyle p_{ij}}$|${\displaystyle C_{\max }}$"هي مشكلة ورشة عمل مكونة من 3 آلات مع أوقات معالجة موحدة، حيث يكون الهدف هو تقليل الحد الأقصى لوقت الإنجاز."

تتكون مدخلات مسألة جدولة ورشة العمل المفتوحة من مجموعة من n مهمة، ومجموعة أخرى من m محطة عمل، وجدول ثنائي الأبعاد يوضح مقدار الوقت الذي يجب أن تقضيه كل مهمة في كل محطة عمل (قد يكون صفرًا). يمكن معالجة كل مهمة في محطة عمل واحدة فقط في كل مرة، ويمكن لكل محطة عمل معالجة مهمة واحدة فقط في كل مرة. مع ذلك، وعلى عكس مسألة ورشة العمل التقليدية ، يمكن أن يختلف ترتيب خطوات المعالجة بحرية. الهدف هو تحديد وقت معالجة كل مهمة في كل محطة عمل، بحيث لا تُخصص مهمتان لنفس محطة العمل في الوقت نفسه، ولا تُخصص أي مهمة لمحطتي عمل في الوقت نفسه، وتُخصص كل مهمة لكل محطة عمل للمدة الزمنية المطلوبة. المقياس المعتاد لجودة الحل هو مدة إنجاز جميع المهام ، أي مقدار الوقت من بداية الجدول (أول تخصيص لمهمة في محطة عمل) إلى نهايته (وقت انتهاء آخر مهمة في آخر محطة عمل).

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

بالنسبة لثلاث محطات عمل أو أكثر، أو ثلاث وظائف أو أكثر، مع أوقات معالجة متفاوتة، فإن جدولة الورشة المفتوحة هي مسألة صعبة من نوع NP . ^{[ 2 ]}

• يُعد جدولة ورش العمل مشكلة مماثلة ولكن مع قيد إضافي آخر - يجب تنفيذ العمليات بترتيب محدد. 
• جدولة التدفق هي جدولة ورشة العمل ولكن معقيد تدفق إضافي - يجب تنفيذ كل عملية على آلة محددة.