Bicriteria Scheduling on Parallel Processors

• Applicant: Professor Dr. Oliver Braun
• Subject Area: Accounting and Finance
• Term: from 2009 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 137031171

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.

• DFG Programme: Research Fellowships
• International Connection: USA
• Host: Professor Ronald L. Graham