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.