Scholarlink

This paper investigates a two-stage online scheduling problem for parallel machines with the goal of minimizing the makespan. The first stage requires packing a set of n unit jobs into M bags. In the second stage, these bags are allocated to \(m\le M\) machines, with the constraint that jobs within the same bag are processed on the same machine. By introducing an elaborate way of packing, we have developed an online algorithm based on the rule of the LPT and demonstrated that it is the optimal algorithm with a competitive ratio of \(\frac{4}{3}\) .

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Simple Algorithm for Scheduling Unit Jobs with Unknown Number of Machines

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Lishi Yu,
  • Zhiyi Tan

摘要

This paper investigates a two-stage online scheduling problem for parallel machines with the goal of minimizing the makespan. The first stage requires packing a set of n unit jobs into M bags. In the second stage, these bags are allocated to \(m\le M\) machines, with the constraint that jobs within the same bag are processed on the same machine. By introducing an elaborate way of packing, we have developed an online algorithm based on the rule of the LPT and demonstrated that it is the optimal algorithm with a competitive ratio of \(\frac{4}{3}\) .