单机双目标排序与调度

　　This book is mainly concerned with single machine bicriteria schedulingproblems . Following a theoretic framework and a literature survey， foursingle machine b icriteria scheduling problems are studied. ？？The first one is a single machine scheduling problem to minimize the totalweigh ted earliness subject to minimal number of tardy jobs. First， severalpropertiesof the problem are discussed in analyzing the problem. Then， aheuristic algori thm of time complexity O（n2） and an efficient branch andbound algorit hm a re proposed. The computational experiments show that theheuristic algorithm is？？effective？？ in terms of quality of the solutionsin most instances while the b ranch and bound algorithm is efficient formedium sized problems. ？？The second one is a single machine scheduling problem with distinct duewindowsto minimize total weighted earliness and tardiness. A mathematicalformulation i s presented and several important properties of the problemare studied. Then anoptimal timing algorithm to decide job completiontimes for a given job sequenc e is proposed. The Tabu search scheme isemployed together with the optimal timi ng algorithm to generate jobsequences and final schedules. Several experimentswere designed andcarried out to demonstrate the performance of the proposed app roach.？？The third one is a single machine common due window scheduling problemin whichjob processing times are controllable with linear costs. Theobjective of the pr oblem is to find a job sequence， a processing time foreach job， and a positionof the common due window to minimize the totalcost of weighted earliness/tardin ess and processing time compression.Several properties of the problem are studi ed and a polynomial timealgorithm of time complexity ？？O（n3） is developed f or solving the problem.？？The last one is concerned with the computational complexity of a singlemachinescheduling problem to minimize total processing plus weighted flowcost. The com putational complexity of the problem has been open for sometwenty years. A posi tive answer to a conjecture for this problem ispresented， showing that it is NP hard at least in the ordinary sense.？？Finally， some concluding remarks and future research directions relevant tothestudies are given， providing a guideline for further research.

暂缺《单机双目标排序与调度》作者简介

Contents
Preface
List of Figures
List of Tables
Chapter 1 Introduction
1??1Introduction to Scheduling Problems
1??2Motivations and the Problems
1??2??1Motivations
1??2??2Problem settings
1??2??3The problems
1??3Outline and Contributions
Chapter 2〖ZK(〗Single Machine Bicriteria Schedulin g:??A Survey
2??1Introduction and Background
2??2〖ZK(〗A Framework of Bicriteria Scheduling Problems
2??2??1〖ZK(〗Nature of the problems: deterministic or sto??chastic
2??2??2Machine environments
2??2??3Performance measures
2??2??4Scheduling criteria
2??2??5Solution approaches
2??2??6〖ZK(〗A framework for single machine bicriteria??scheduling problems
2??3 A Summary of Single Machine Bicriteria Scheduling??Literature
2??3??1Pareto optimization
2??3??2Hierarchical optimization
2??3??3Weighted??sum optimization
2??3??4〖ZK(〗Earliness and Tardiness Scheduling Models
2??3??5〖ZK(〗Other bicriteria related scheduling research
2??3??6Observations
2??4Conclusions
Chapter 3〖ZK(〗Single Machine Scheduling to Minimize??Total〖KG??2〗Weighted〖KG??2〗Earliness〖KG??2〗Subject〖KG??2〗to??Minimal Number of Tardy Jobs
Contents
3??1Introduction
3??2Notations and Basic Properties of the Problem
3??3A Heuristic and the Polynomially Solvable Cases
3??4A Branch and Bound Algorithm
3??5Computational Experiments
3??6Conclusions
Chapter 4〖ZK(〗Tabu Search for Total Weighted Earliness and Tardiness Minimization on a Single Machine with Distinct Due Windows
4??1Introduction
4??2Problem Description and the Properties
4??3The Optimal Timing Algorithm
4??4〖ZK(〗Sequencing by Tabu Search
4??4??1Neighborhood
4??4??2Tabu list
4??4??3Aspiration criterion
4??4??4Initial solutions and the stopping criteria
4??4??5〖ZK(〗Incorporating optimality properties into the TS procedure
4??5〖ZK(〗Computational Experiments
4??5??1Problem instance generation
4??5??2Computational results
4??6Conclusions
Chapter 5〖ZK(〗Single Machine Common Due Window Sche duling with Controllable Job Processing??Times
5??1Introduction
5??2Problem Formulation
5??3Properties of the Problem
5??4An Algorithm to Solve the Problem
5??5Conclusions
Chapter 6〖ZK(〗Single Machine Scheduling to Minimize Total Compression plus Weighted Flow??Cost Is NP??Hard
6??1Introduction
6??2Problem Description
6??3NP??Hardness of the Problem
Chapter 7Conclusions and Outlook
7??1Conclusions
7??2Outlook of the Future Research
References