Some dominance rules are proposed for the problems of scheduling N jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz' s branch and bound scheme ...Some dominance rules are proposed for the problems of scheduling N jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz' s branch and bound scheme are developed including the dominance rules where the objective is to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules.展开更多
A single machine scheduling problem involving fuzzy due dates and fuzzy precedence constraints is investigated. The fuzzy precedence reflects the satisfaction level with respect to precedence between two jobs. A membe...A single machine scheduling problem involving fuzzy due dates and fuzzy precedence constraints is investigated. The fuzzy precedence reflects the satisfaction level with respect to precedence between two jobs. A membership function is associated with each job Ji, which describes the degree of satisfaction with respect to completion time of Ji. For the bi-criteria scheduling problem, an 0 ( n^3 ) algorithm is proposed for finding nondominated solutions.展开更多
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.展开更多
文摘Some dominance rules are proposed for the problems of scheduling N jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz' s branch and bound scheme are developed including the dominance rules where the objective is to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules.
文摘A single machine scheduling problem involving fuzzy due dates and fuzzy precedence constraints is investigated. The fuzzy precedence reflects the satisfaction level with respect to precedence between two jobs. A membership function is associated with each job Ji, which describes the degree of satisfaction with respect to completion time of Ji. For the bi-criteria scheduling problem, an 0 ( n^3 ) algorithm is proposed for finding nondominated solutions.
文摘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.