Bicriteria Scheduling on Parallel Processors

调度是一个决策过程，在制造业和服务业中发挥着重要作用。在生产、采购、运输和分销以及信息处理和通信方面都有大量的应用。通常，调度包括分配有限的资源来处理任务。确定性调度理论起源于20世纪50年代。在过去的几年中，由于多标准调度问题具有巨大的应用潜力，人们对多标准调度问题越来越感兴趣：许多现代工业过程非常复杂，仅应用调度的一个最优性标准并不能满足决策者。例如，决策者可能需要同时考虑几个标准，例如最大完成时间、客户满意度、准时交付和在制品库存。沿着这条线，我们研究了一个关于双准则优化目标的经典调度问题。更详细地说，我们研究了必须在并行操作的相同处理器上调度一组独立作业的问题。我们考虑两个标准：最小化任何作业的最大完成时间和最小化作业抢占的数量。这是因为，一般来说，少量的先发制人具有降低在制品库存、降低物料搬运成本、减少工装更换、提高质量、降低运输成本以及简化物料和人工的生产计划等优势。该研究方案开辟了一个研究领域，将具有任意数量抢占的调度问题推广到具有有限数量抢占的调度问题。

Scheduling is a decision-making process that plays an important role in manufacturing and in service industries. There is a huge number of applications in production, procurement, transportation and distribution as well as in information processing and communication. In general, scheduling consists in the allocation of limited resources to the processing of tasks. Deterministic scheduling theory has its beginnings in the 1950s. In the last few years, there has been an increasing interest in multicriteria scheduling problems because of their great application potential: Many modern industrial processes are so complex that applying only one optimality criterion of a schedule does not satisfy a decision maker. As an example, decision makers may need to consider several criteria at the same time such as the maximum completion time, customer satisfaction, on time delivery and work-in-process inventory. Along this line, we investigate a classical scheduling problem with respect to a bicriteria optimization goal. In more detail, we investigate the problem in which a set of independent jobs has to be scheduled on identical processors that operate in parallel. We consider two criteria: Minimizing the maximum completion time of any job and minimizing the number of job preemptions. This is because a small number of preemptions, in general, has advantages such as lower work-in-process inventories, reduced material handling costs, fewer tooling changes, quality improvements, lower transportation costs and simplied production planning of materials and labor. The research proposal opens a field of research where scheduling problems with arbitrary number of preemptions are generalized to scheduling problems with limited number of preemptions.