In this paper, an integrated machine scheduling with its Due date setting problem has been considered. It is assumed that the machine is subject to some kind of random unavailability. Due dates should be set in an attractive and reliable manner, implying that they should be short and possible to be met. To this end, first, long Due dates are penalized in the objective function. Then, for each customer order, the probability of meeting his/her promised Due date is forced to be at least as large as his/her required service level. To handle this integrated problem, first, the optimal Due date formula for any arbitrary sequence is derived. By using this formula, the mathematical programming formulation of the problem, including a nonlinear non-convex expression, is developed. By defining a piecewise linear under-estimator, the solutions of the resultant mixed integer linear programming formulation have become the lower bounds of the problem. Dynasearch is a very efficient heuristic utilizing the dynamic programming approach to search exponential neighborhoods in the polynomial time. An iterated dynasearch heuristic is developed for the sequencing part of the problem. Each generated sequence is evaluated by computing its optimal Due dates using the above-mentioned formula. Numerical results confirmed the high quality of the solutions found by this algorithm, as compared with the lower bound.