本研究探討一釋放時間(release times)存在與否之多績效衡量單機排程問題。目標是在受限於各種不同延遲作業數目條件下，求得最小化加權早交時間與延遲時間。問題假設各自具有不同的早交與延遲加權權重的n個作業有相同的到期日(due date )。本研究提供二演算法於各種延遲作業數目之限制下，分別針對存在釋放時間(release time)限制與否之前提，有效地產生Pareto最佳解。演算法的正確性與運算執行時間亦於本研究中被討論。另外也呈現本研究之演算法可排除大部份分枝樹(branching tree)內的節點以有效地找到解答。 This dissertation investigates a single-machine scheduling problem without and with release time restriction. The objective is to minimize the summation of the weighted earliness and tardiness, subject to the number of tardy jobs. There are n jobs with a given common due date and each job has different weights for earliness and tardiness. Two algorithms are proposed to efficiently generate Pareto-optimal solutions for any possible number of tardy jobs without and with release time restriction. We also work with the benchmark problems discussed in Biskup and Feldmann [3]. The accuracy and run time of our algorithms are discussed. In addition the results show that the proposed algorithms can eliminate most nodes in the branching tree to efficiently find solutions.
