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...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 Ⅱ),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 Ⅰ.Computational results are presented to show the efficiency and the robustness of these heuristics.展开更多
文摘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 Ⅱ),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 Ⅰ.Computational results are presented to show the efficiency and the robustness of these heuristics.
