Scheduling Problems With Variable Processing Times And Resource Constraints

In actual production process, if the job is processed, the actual processing time may not be a fixed constant. The actual processing time may be changed by the influence of the factors that are the efficiency of production, machine deteriorating, energy fuel consumption and resource constraints. In addition, in some models, the influence of some practical factors, for example: a job cost is too high or the processing time is too long, it will lead to additional costs, so we need to consider whether the job is processed. If the job is rejected, we will need to pay for an additional punishment.This paper considers the influence of the actual factors that include the learning effects, deteriorating factors, resource constraints, and the cost of refusing,considering the scheduling problems that the processing time is for linear and convex with resource allocation, etc. Specific content summarized as follows:1) This paper considers unrelated parallel-machine scheduling problems with position dependent deteriorating jobs and resource allocation. In this paper, we focus on the two unrelated parallel machine problems that one objective function is the weighted sum of total load, total completion time, total absolute differences in completion time and total resource cost, and another function is the weighted sum of total load, total waiting time, total absolute differences in waiting times and total resource cost, respectively. The objectives are to find the optimal sequence of jobs and the optimal resource allocation, separately. We show that the problems can be transformed into corresponding assignment problems, then prove that the proposed problems can be solved in polynomial time under the proposed model.2)This paper also considers unrelated parallel-machine scheduling problems with deteriorating jobs and convex resource allocation. The actual processing time of the job is a convex resource allocation function that based on the basic processing time,the starting processing time, the actual processing position. This paper discuss two scheduling problems that the objective function is the sum of completion time and resources, and another is the sum of the completion time and, waiting time and the allocation of resource problem. We show that the problems can be transformed into corresponding assignment problems, then prove that the problems can be solved in polynomial time under the proposed model.3)This paper considers the rejection and two kinds of resource allocation of single machine scheduling problems with time window to assign. Start processing time,processing location and resource allocation amount jointly determine the actual processing time. Linear resource allocation and convex resource allocation are divided into two cases. The objective function is the sum of earliness, the number of tardiness, the starting time of the due date window, the width of the due date window,resource consumption and rejections penalties. Algorithm is proposed to determine the optimal scheduling sequence and resource allocation problems.