Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical...Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical situations,it is found that some jobs fail to be processed prior to the pre-specified thresholds,and they often consume extra deteriorating time for successful accomplishment. Their processing times can be characterized by a step-wise function. Such kinds of jobs are called step-deteriorating jobs. In this paper,parallel machine scheduling problem with stepdeteriorating jobs( PMSD) is considered. Due to its intractability,four different mixed integer programming( MIP) models are formulated for solving the problem under consideration. The study aims to investigate the performance of these models and find promising optimization formulation to solve the largest possible problem instances. The proposed four models are solved by commercial software CPLEX. Moreover,the near-optimal solutions can be obtained by black-box local-search solver LocalS olver with the fourth one. The computational results show that the efficiencies of different MIP models depend on the distribution intervals of deteriorating thresholds, and the performance of LocalS olver is clearly better than that of CPLEX in terms of the quality of the solutions and the computational time.展开更多
This paper deals with single-machine scheduling problems with a more general learning effect based on sum-of-processing-time. In this study, sum-of-processing-time-based learning effect means that the processing time ...This paper deals with single-machine scheduling problems with a more general learning effect based on sum-of-processing-time. In this study, sum-of-processing-time-based learning effect means that the processing time of a job is defined by a decreasing function of the total normal processing time of jobs that come before it in the sequence. Results show that even with the introduction of the sum-of-processing-time-based learning effect to job processing times, single-machine makespan minimization problems remain polynomially solvable. The curves of the optimal schedule of a total completion time minimization problem are V-shaped with respect to iob normal orocessinz times.展开更多
This paper studies a single machine scheduling problem with time-dependent learning and setup times. Time-dependent learning means that the actual processing time of a job is a function of the sum of the normal proces...This paper studies a single machine scheduling problem with time-dependent learning and setup times. Time-dependent learning means that the actual processing time of a job is a function of the sum of the normal processing times of the jobs already scheduled. The setup time of a job is proportional to the length of the already processed jobs, that is, past-sequence-dependent (psd) setup time. We show that the addressed problem remains polynomially solvable for the objectives, i.e., minimization of the total completion time and minimization of the total weighted completion time. We also show that the smallest processing time (SPT) rule provides the optimum sequence for the addressed problem.展开更多
Fast computation methods are needed for the heuristics of flow shop scheduling problems in practical manufacturing environments. This paper describes a generalized flow shop model, which is an extension of the classic...Fast computation methods are needed for the heuristics of flow shop scheduling problems in practical manufacturing environments. This paper describes a generalized flow shop model, which is an extension of the classical model, in which not all machines are available at time zero. The general completiontime computing method is used to compute completion time of generalized flow shops. The transform classical flow shop to generalized shop （TCG） method is used to transform classical schedules into generalized schedules with less jobs. INSERT and SWAP, extended from job-insertion and pair-wise exchange which are fundamental procedures used in most heuristics for classical flow shops, reduce the CPU time by 1/2 and 1/3, respectively. The CPU time of 14 job-insertion and pair-wise exchange-based heuristics are analyzed with and without the TCG method. The results show that TCG considerably reduces the CPU time展开更多
基金National Natural Science Foundation of China(No.51405403)the Fundamental Research Funds for the Central Universities,China(No.2682014BR019)the Scientific Research Program of Education Bureau of Sichuan Province,China(No.12ZB322)
文摘Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical situations,it is found that some jobs fail to be processed prior to the pre-specified thresholds,and they often consume extra deteriorating time for successful accomplishment. Their processing times can be characterized by a step-wise function. Such kinds of jobs are called step-deteriorating jobs. In this paper,parallel machine scheduling problem with stepdeteriorating jobs( PMSD) is considered. Due to its intractability,four different mixed integer programming( MIP) models are formulated for solving the problem under consideration. The study aims to investigate the performance of these models and find promising optimization formulation to solve the largest possible problem instances. The proposed four models are solved by commercial software CPLEX. Moreover,the near-optimal solutions can be obtained by black-box local-search solver LocalS olver with the fourth one. The computational results show that the efficiencies of different MIP models depend on the distribution intervals of deteriorating thresholds, and the performance of LocalS olver is clearly better than that of CPLEX in terms of the quality of the solutions and the computational time.
文摘This paper deals with single-machine scheduling problems with a more general learning effect based on sum-of-processing-time. In this study, sum-of-processing-time-based learning effect means that the processing time of a job is defined by a decreasing function of the total normal processing time of jobs that come before it in the sequence. Results show that even with the introduction of the sum-of-processing-time-based learning effect to job processing times, single-machine makespan minimization problems remain polynomially solvable. The curves of the optimal schedule of a total completion time minimization problem are V-shaped with respect to iob normal orocessinz times.
文摘This paper studies a single machine scheduling problem with time-dependent learning and setup times. Time-dependent learning means that the actual processing time of a job is a function of the sum of the normal processing times of the jobs already scheduled. The setup time of a job is proportional to the length of the already processed jobs, that is, past-sequence-dependent (psd) setup time. We show that the addressed problem remains polynomially solvable for the objectives, i.e., minimization of the total completion time and minimization of the total weighted completion time. We also show that the smallest processing time (SPT) rule provides the optimum sequence for the addressed problem.
基金Supported by the National Key Basic Research and Development Program (973) of China (No. 2002CB312205), the China Postdoctoral Science Foundation (No. 2003033150), the Natural Science Foundation of Heilongjiang Province (No. F0207), the Youth Foundation of Harbin City (No. 2002AFQXJ033), and the Science and Technology Foundation of Heilongjiang Education Bureau (No. 10531056)
文摘Fast computation methods are needed for the heuristics of flow shop scheduling problems in practical manufacturing environments. This paper describes a generalized flow shop model, which is an extension of the classical model, in which not all machines are available at time zero. The general completiontime computing method is used to compute completion time of generalized flow shops. The transform classical flow shop to generalized shop （TCG） method is used to transform classical schedules into generalized schedules with less jobs. INSERT and SWAP, extended from job-insertion and pair-wise exchange which are fundamental procedures used in most heuristics for classical flow shops, reduce the CPU time by 1/2 and 1/3, respectively. The CPU time of 14 job-insertion and pair-wise exchange-based heuristics are analyzed with and without the TCG method. The results show that TCG considerably reduces the CPU time
