Lot scheduling on a single machine to minimize total weighted completion time

¹ Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, P.R. China
² School of Management, Xi’an Jiaotong University, Xi’an 710049, P.R. China
³ School of Economics & Management, Tongji University, Shanghai 200092, P.R. China

^* Corresponding author: mingliu@tongji.edu.cn

Received: 16 January 2024
Accepted: 10 April 2025

Abstract

Lot scheduling is one of the important production patterns in modern manufacturing systems. Each lot processes simultaneously one or more customer orders with a total size no more than the fixed lot capacity, consuming a uniform lot processing time. In this work we consider the single machine lot scheduling environment where any order can be split and processed in consecutive lots. The objective is to minimize total weighted completion time. We first prove the NP-hardness of the considered problem, and propose a polynomial-time algorithm with approximation ratio equal to the ratio of the largest to the smallest order weight. Moreover, we explore two special cases. For the first case where the total size of all the orders is at most twice of the lot capacity, a dynamic programming algorithm is provided. In the last special case, the sizes and weights of orders are in reverse-agreeable, i.e., a larger size of an order implies an equal or smaller weight. We prove that processing orders in the non-increasing sequence of their weights results in an optimal schedule, implying that the case is solvable in polynomial time. Finally, experimental results demonstrate the effectiveness of the approximation algorithm.