Parallel machine scheduling problem with machine cost to minimize the maximal lateness

In this paper, we assumed that machines have different energy consumptions or maintenance costs in the context of green manufacturing, and tried to solve the parallel machine scheduling problem under the condition of cost constraints. To minimize the maximum lateness, an integer programming model MIP was established and an improved algorithm for EDD (earliest due date firstly) - MEDD was designed. Then the feasibility of the MEDD algorithm was proved under the condition of cost constraints, and the worst error bound of the algorithm was also analyzed theoretically. By giving an example, we proved the feasibility of the algorithm. And its performance was verified by a large number of random data experiments. For a small scale, the solution of MEDD was compared with the exact solution of MIP. While the exact solution of MIP is too hard to obtain when it comes to a large scale, the optimal value of MLP of the linear programming relaxation model corresponding to MIP was taken as the lower bound to measure the solution of MEDD algorithm. All these results showed a great effectiveness of MEDD algorithm.