زمان بندی با مهلت معین

زمان بندی با مهلت معین

در این مسئله زمان بندی، هر کاری در یک واحد زمانی به پایان می رسد و دارای یک مهلت و سود معین است. اگر هر کار پیش از مهلت معین یا در آن مدت انجام شود، سود مورد نظر به دست می آید. هدف، زمان بندی کارها به نحوه ای است که سود بیشینه به دست آید. لازم نیست همه کارها زمان بندی شوند. نیازی نیست هر زمان بندی را که در آن یک کار پس از مهلت مقرر آن برنامه ریزی شده است، در نظر بگیریم، زیرا آن زمان بندی همان قدر بهره وری دارد که برای آن کار اصلا زمان بندی نشده باشد.چنین زمان بدنی را غیر ممکن می خوانیم.