Abstract
Production scheduling arranges the production activities for various jobs under the limitation of scarce resources. This study discusses a single-machine production scheduling problem. The known attributes of a job include processing time, ready date, due date, and weight. Different jobs are allowed to have different ready dates and due dates. A job is either totally completed between its ready date and its due date on a single machine or totally rejected. The problem this study investigates is a non-preemptive single machine scheduling problem with the objective of maximizing total weight generated by completed jobs. Such a problem is called throughput maximization problem in previous literatures. This study develops three methods to solve the problem: (1) a heuristic method; (2) a mixed integer programming; and (3) a brand-and-bound method. The heuristic method provides an initial solution for the mixed integer programming and the brand-and-bound method. To reduce computation time of the branch-and-bound method, this study develops four dominance rules and bounding approach using an LP-relaxation formulation. From the results of experiments, the computation time of mixed integer programming is larger than other methods. Also, partial orderings can provide a solution near an optimal solution. This shows that if we use the partial orderings before solving a problem by the branch-and-bound method, we can immediately obtain an objective value near the optimal solution. Most of fathom rules are used in high frequency. Thus, two partial orderings, four dominance rules, and bounding approach using an LP-relaxation formulation can reduce computation time of the branch-and-bound method effectively.