| SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （Part Ⅱ Heuristics for the General Case） |
| |
| 作者姓名： | Foulds L.R. TangGuochun |
| |
| 作者单位： | [1]Dept.ofManagementSystems,Univ,otWaikato,Hamilton,NewZealand, [2]Dept.ofManagement,ShanghaiSecondPolytechnicUniv.,Shanghai200002. |
| |
| 摘 要： | A single machine scheduling problem with controllable processing times and compression costs is considered. The objective is to find an optimal sequence to minimize the cost ofcompletion times and the cost of compression. The complexity of this problem is still unknown.In Part Ⅱ of this paper,the authors have considered a special case where the compression timesand the compression costs are equal among all jobs. Such a problem appears polynomiafiy solvable by developing an O(n^2) algorithm. In this part(Part Ⅱ ),a general case where the controllable processing times and the compression costs are not equal is discussed. Authors proposehere two heuristics with the first based on some previous work and the second based on the algorithm developed in Part Ⅱ . Computational results are presented to show the efficiency and therobustness of these heuristics.
|
| 关 键 词： | 机器时序 处理时间 费用压缩 计算机辅助软件 理想序列 |
Single machine scheduling with controllable processing times and compression costs |
| |
| Foulds,L.R. TangGuochun.Single machine scheduling with controllable processing times and compression costs[J].Applied Mathematics A Journal of Chinese Universities,1999,14(1):75-84. |
| |
| Authors: | L R Foulds Tang Guochun |
| |
| Institution: | 1. Dept. of Management System, Univ. of Waikato, Hamilton, New Zealand
2. Dept. of Management, Shanghai Second Polytechnic Univ., 200002, Shanghai
|
| |
| Abstract: | A single machine scheduling problem with controllable processing times and compression costs is considered. The objective is to find an optimal sequence to minimize the cost of completion times and the cost of compression. The complexity of this problem is still unknown. In Part I of this paper, the authors have considered a special case where the compression times and the compression costs are equal among all jobs. Such a problem appears polynomially solvable by developing an O(n 2 ) algorithm. In this part(Part II), a general case where the controllable processing times and the compression costs are not equal is discussed. Authors propose here two heuristics with the first based on some previous work and the second based on the algorithm developed in Part I. Computational results are presented to show the efficiency and the robustness of these heuristics. |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
