Track: Operations Research

Abstract

We consider the bicriteria scheduling problem of minimizing the total tardiness and total flowtime on a single machine. This problem, which is known to be NP-hard, is important in practice, as the former criterion conveys the customer’s position, and the latter reflects the manufacturer’s perspective for optimal resources utilization. The simultaneous optimization approach was adopted. Two heuristics to minimize the Linear Composite Objective Function (LCOF) of the two objectives were proposed. The utility of the proposed models was demonstrated through computational experiments and comparative analyses against existing solution methods and the Branch and Bound (BB) method. The results show that the proposed models yield efficient and near optimal schedules in most cases and perform better than the existing heuristics in the literature.We consider the bicriteria scheduling problem of minimizing the total tardiness and total flowtime on a single machine. This problem, which is known to be NP-hard, is important in practice, as the former criterion conveys the customer’s position, and the latter reflects the manufacturer’s perspective for optimal resources utilization. The simultaneous optimization approach was adopted. Two heuristics to minimize the Linear Composite Objective Function (LCOF) of the two objectives were proposed. The utility of the proposed models was demonstrated through computational experiments and comparative analyses against existing solution methods and the Branch and Bound (BB) method. The results show that the proposed models yield efficient and near optimal schedules in most cases and perform better than the existing heuristics in the literature.