The order picking operations in a physical distribution center
and the specialized testing stations in an automobile plant
containing a large quality control center are open-shop
scheduling. These open-shop schedules have no restrictions on
the processing order of the jobs. Minimizing the total
tardiness time, the total tardy cost, and the penalty of total
earliness and total tardiness are the three concerned major
criteria in an open-shop involving due dates. The problem of
minimizing the total tardiness has been proved to be NP-hard.
Therefore, the problems of minimizing the total tardy cost, or
the penalty of total earliness and total tardiness in an m-
machine deterministic nonpreemptive open-shop are also NP-hard.
A network structure based on the spanning tree is constructed
in this dissertation to simplify the mathematical model of a
nonpreemptive open-shop problem with an objective to minimize
the three criteria. The idle time rule developed in this
dissertation serves as the decision criterion. In the studied
criteria, two proposed heuristics are compared with SPT, EDD,
SLACK, and MWSTR/EST methods, using 14,400 cases. The test
cases are composed of different features, such as the number of
jobs, the number of machines, the tardiness factor, and the
range of due-date. Experimental results indicate that the
proposed heuristics perform much more efficiently than the
other four methods under the criteria studied. In this
dissertation, the characteristic of the experimental results
has also been studied to verify the factors that have influence
on the solution quality for the proposed heuristic approaches.