This paper presents an algorithm for finding an improved machine-based lower bound of make-span by introducing the concept of maximum effective preprocessing time for a machine. The usefulness is indicated by developing machino-based lower bounds without presequence of jobs. Numerical examples illustrate the improvement in the value of machine-based bound which in turn improves the global lower bound for permutation flows hop problems only.