Bicriterion total flowtime and maximum tardiness minimization for an order scheduling problem

An order scheduling problem arises in numerous production scheduling environments. Makespan, mean flow time, and mean tardiness are the most commonly discussed and studied measurable criteria in the research community. Although the order scheduling model with a single objective has been widely studied, it is at odds with real-life scheduling practices. In practice, a typical manager must optimize multiple objectives. A search of the literature revealed that no articles had addressed the issue of optimizing an order scheduling problem with multiple objectives. Therefore, an order scheduling model to minimize the linear sum of the total flowtime and the maximum tardiness is introduced in this study. Specifically, several dominance relations and a lower bound are derived to expedite the search for the optimal solution. Three modified heuristics are proposed for finding near-optimal solutions. A hybrid iterated greedy algorithm and a particle swarm colony algorithm are proposed to solve this problem. Finally, a computational experiment is conducted to evaluate the performances of all proposed algorithms.