工件帶拒絕費用的兩個單機排序問題

1、曲阜師范大學碩士學位 i 曲阜師范大學研究生學位論文原創(chuàng)性說明 （根據(jù)學位論文類型相應地在“□”劃“√”） 本人鄭重聲明：此處所提交的博士□/碩士□論文《 工件帶拒絕費用的兩個單機排序問題 》，是本人在導師指導下，在曲阜師范大學攻讀博士□/碩士□學位期間獨立進行研究工作所取得的成果。論文中除注明部分外不包含他人已經發(fā)表或撰寫的研究成果。對本文的研究工作做出重要貢獻的個人和集體，均已在文中以明確的方式注明。本聲明的法律結果

2、將完全由本人承擔。 作者簽名： 日期： 曲阜師范大學研究生學位論文使用授權書 （根據(jù)學位論文類型相應地在“□”劃“√”） 《 工件帶拒絕費用的兩個單機排序問題 》系本人在曲阜師范大學攻讀博士□/碩士□學位期間，在導師指導下完成的博士□/碩士□學位論文。本論文的研究成果歸曲阜師范大學所有，本論文的研究內容不得以其他單位的名義發(fā)表。本人完全了解曲阜師范大學關于保

3、存、使用學位論文的規(guī)定，同意學校保留并向有關部門送交論文的復印件和電子版本，允許論文被查閱和借閱。本人授權曲阜師范大學，可以采用影印或其他復制手段保存論文，可以公開發(fā)表論文的全部或部分內容。 作者簽名： 日期： 導師簽名： 日期： 曲阜師范大學碩士學位 iii Two Single-Machine Scheduling Pro

4、blems with Rejection Abstract In the classical scheduling model, we tend to assume that the machine must be used for processing all jobs within the given processing time. But in many practical applications, a job could n

5、ot be processed if its processing time or processing cost is very large. Jobs are either rejected, in which case the rejection penalty has to be paid or received and processed on the machine. The objective functions are

6、not the only the makespan and maximum lateness. The penalty should also be considered. We call it Scheduling with rejection. Three chapters are included in this thesis. In the first chapter, some notation, definition and

7、 basic background information about the subject are introduced. In the second chapter, Scheduling problems with family jobs and rejection on a (batching) single-machine are studied for the first time in this paper. We co

8、nsider of several conditions with objective function to minimize maximum completion time and provide their nature. For problems max 1, , fg jj ss family jobs rej C eÎ- +åand max 1, , , fg jj ss family jobs re

9、j b C eÎ- +å , the approximation algorithms and some qualities are given and proved. In the third chapter, Scheduling problems with family jobs and rejection on a s-batch single-machine are studied for the firs

10、t time in this paper. We consider of several conditions with objective function to minimize maximum completion time and provide their nature. For problem max 1, , , , fg jj ss family jobs rej s batch b n C eÎ- - ? &