Suggesting Approximation and Exact Algorithms to Solve New Tri-Criteria Machine Scheduling Problems

This study presents the multi criteria single-machine model. The machine scheduling problem (MSP) for n tasks on a single machine involves minimizing a function of three criteria: total completion time (C_j), maximum earliest (E_max), and tardiness (〖ΣT〗_j), This is an NP-hard issue. Within this work's theoretical section, we present the mathematical formulation of The presented topic then highlights the usefulness of the dominance rule (DR), which may be used to develop effective solutions. While in the practical part, one of the important exact methods; The proposed MSP tricriteria are solved by applying the Branch and Bound (BAB) method, which finds a set of efficient solutions for 1//F(ΣC_j ,ΣT_j ,E_max) up to n=100 jobs. The BAB approach finds the efficient solutions for the issue in an acceptable amount of time. In addition, we provide two heuristic approaches to address the problem in order to obtain appropriate approximations. The two proposed approaches' good performance is demonstrated by the practical experiments.