A benders decomposition-based heuristic algorithm framework for unrelated parallel machine scheduling problem with weighted maximum earliness and tardiness

摘要

Problems about parallel machines are researched a lot and have a wide application. An unrelated parallel machine scheduling problem is discussed in this paper: there're m unrelated parallel machines that have different processing speeds and opening costs. N jobs are assigned to the machines, meeting distinct due windows. The objective is to minimize the total cost including the machine opening cost and the cost related to maximum earliness and tardiness. The scheduling progress takes both machine utilization and customer satisfaction into consideration. The proposed method in this paper is a benders decomposition-based heuristic algorithm that can solve mixed-integer linear programming problem efficiently. The algorithm is based on a partition of the problem, which is suitable to solve our problem. The algorithm framework is established to solve large-scale problems.