| Single machine stochastic JIT scheduling problem subject to machine breakdowns |
| |
| 作者单位： | TANG HengYong~ ZHAO ChuanLi CHENG CongDian College of Mathematics and Systems Science，Shenyang Normal University，Shenyang，110034，China |
| |
| 摘 要： | In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.
|
| 收稿时间： | 3 November 2005 |
| 修稿时间： | 24 July 2007 |
Single machine stochastic JIT scheduling problem subject to machine breakdowns |
| |
| Authors: | Tang HengYong Zhao ChuanLi Cheng CongDian |
| |
| Institution: | (1) College of Mathematics and Systems Science, Shenyang Normal University, Shenyang, 110034, China |
| |
| Abstract: | In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem. |
| |
| Keywords: | stochastic JIT scheduling machine breakdowns preemptive-resume preemptive-repeat sum of squared deviations of the expected completion times from the due date |
| 本文献已被 CNKI SpringerLink 等数据库收录！ |
