In manufacturing, it is common for manufacturers to receive customized orders with varying quantities and priority levels. This work focuses on the situation where orders are processed in lots with unified capacity on a single machine. Each lot has the potential to accommodate multiple orders, and if necessary, any order can be split and processed in consecutive lots. Each order is characterized by its size and weight. The objective of the problem is to minimize the maximum weighted completion time. By proving that processing orders in non-increasing sequence of their weights yields an optimal schedule, we conclude that the problem can be solved in polynomial time.

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

Single Machine Lot Scheduling to Minimize Maximum Weighted Completion Time

  • Feifeng Zheng,
  • Na Li,
  • Ming Liu,
  • Yinfeng Xu

摘要

In manufacturing, it is common for manufacturers to receive customized orders with varying quantities and priority levels. This work focuses on the situation where orders are processed in lots with unified capacity on a single machine. Each lot has the potential to accommodate multiple orders, and if necessary, any order can be split and processed in consecutive lots. Each order is characterized by its size and weight. The objective of the problem is to minimize the maximum weighted completion time. By proving that processing orders in non-increasing sequence of their weights yields an optimal schedule, we conclude that the problem can be solved in polynomial time.