Abstract Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by reallocating resources. In ...Abstract Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by reallocating resources. In this paper, authors consider a machine scheduling problem with controllable processing times. In the first part of this paper, a special case where the processing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O(n 2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case. An effective heuristic to the general problem will be presented.展开更多
Due date quotation and scheduling are important tools to match demand with production capacity in the MTO (make-to-order) environment. We consider an order scheduling problem faced by a manufacturing f'trm operatin...Due date quotation and scheduling are important tools to match demand with production capacity in the MTO (make-to-order) environment. We consider an order scheduling problem faced by a manufacturing f'trm operating in an MTO environment, where the firm needs to quote a common due date for the customers, and simultaneously control the processing times of customer orders (by allocating extra resources to process the orders) so as to complete the orders before a given deadline. The objective is to minimize the total costs of earliness, tardiness, due date assignment and extra resource consumption. We show the problem is NP-hard, even if the cost weights for controlling the order processing times are identical. We identify several polynomially solvable cases of the problem, and develop a branch and bound algorithm and three Tabu search algorithms to solve the general problem. We then conduct computational experiments to evaluate the performance of the three Tabu-search algorithms and show that they are generally effective in terms of solution quality.展开更多
文摘Abstract Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by reallocating resources. In this paper, authors consider a machine scheduling problem with controllable processing times. In the first part of this paper, a special case where the processing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O(n 2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case. An effective heuristic to the general problem will be presented.
文摘Due date quotation and scheduling are important tools to match demand with production capacity in the MTO (make-to-order) environment. We consider an order scheduling problem faced by a manufacturing f'trm operating in an MTO environment, where the firm needs to quote a common due date for the customers, and simultaneously control the processing times of customer orders (by allocating extra resources to process the orders) so as to complete the orders before a given deadline. The objective is to minimize the total costs of earliness, tardiness, due date assignment and extra resource consumption. We show the problem is NP-hard, even if the cost weights for controlling the order processing times are identical. We identify several polynomially solvable cases of the problem, and develop a branch and bound algorithm and three Tabu search algorithms to solve the general problem. We then conduct computational experiments to evaluate the performance of the three Tabu-search algorithms and show that they are generally effective in terms of solution quality.