Search

This paper considers a single-machine scheduling problem where jobs have multiple slack due-date assignments, i.e., some jobs have a common flow allowance and all jobs have m (m > 0 is a given constant) common flow allowances. The objective is to determine the multiple common flow allowances and optimal job sequence that minimizes the weighted sum of earliness-tardiness penalty and slack due-date assignment cost, where the weights only depend on their positions in a sequence, i.e., the position-dependent weights. Optimal properties are given for this problem, and then the problem is shown to be polynomially solvable when the number of multiple slack due-date assignments is a given constant. The model with multiple slack due-date assignments can also be extended to position (time)-dependent scheduling. [ABSTRACT FROM AUTHOR]

In this paper, we consider two single-machine scheduling problems with deteriorating jobs and controllable processing time. The job processing time is a function of its starting time and resource allocation. For the convex resource function, a bicriteria analysis is provided, where the first (respectively, second) criteria is to minimize total weighted completion time (respectively, total resource consumption cost). The first problem is to minimize the weighted sum of the total weighted completion time and the total resource consumption cost. The second problem is to minimize the total weighted completion time subject to the total resource consumption cost is bound. These both problems are NP-hard, we propose some heuristic algorithms and a branch-and-bound algorithm to solve the problems. [ABSTRACT FROM AUTHOR]

In this paper, we address single-machine scheduling with sum of logarithm processing times-based learning effect. Under exponential past-sequence-dependent delivery times, we proved that the makespan and total completion time minimizations can be solved by the smallest processing time (SPT) first rule. Under the agreeable weight condition and agreeable due date condition, we show that the total weighted completion time minimization and maximum tardiness minimization can be solved in polynomial time, respectively. [ABSTRACT FROM AUTHOR]

This paper concentrates on the single-machine scheduling problem with past-sequence-dependent setup times and general truncated learning effects, where the job processing times are non-increasing function of their positions in a sequence. Under common, slack and different (unrestricted) due-date assignments, our goal is to minimize the weighted sum of number of early/tardy jobs and due-date assignment cost, where the weight is not related to the job but to a position, i.e., the position-dependent weight. Under the three due-date assignments, some optimal properties and three optimal solution algorithms are proposed to solve these problems, respectively. [ABSTRACT FROM AUTHOR]

In this paper, we consider scheduling problems with slack (different) due-window assignment and time-dependent processing times. The processing time functions are all a proportional linear increasing function of time. On a single-machine setting, the goal is to minimize a cost function that includes earliness, tardiness, due-window starting time and size, and the number of early and tardy jobs. Some relevant optimality properties and polynomial time solution algorithms are proposed to solve these two problems. [ABSTRACT FROM AUTHOR]

We consider a single machine scheduling problem with slack due date assignment in which the actual processing time of a job is determined by its position in a sequence, its resource allocation function, and a rate-modifying activity simultaneously. The problem is to determine the optimal job sequence, the optimal common flow allowance, the optimal amount of the resource allocation, and the position of the rate-modifying activity such that the two constrained optimization objective cost functions are minimized. One is minimizing the total penalty cost containing the earliness, tardiness, common flow allowance subject to an upper bound on the total resource cost, the other is minimizing the total resource cost subject to an upper bound on the total penalty cost. For two optimization problems, we show that they can be solved in optimal time, respectively. [ABSTRACT FROM AUTHOR]

Scheduling problems with variable processing times and past-sequence-dependent delivery times are considered on a single-machine. The delivery times of jobs depend on their waiting times of processing. A job's actual processing time depends on its position in a sequence, its starting time and its allocation of non-renewable resources. Under the linear resource consumption function, the goal (version) is to determine the optimal sequence and optimal resource allocation such that the sum of scheduling cost and total resource consumption cost is minimized. Under the convex resource consumption function, three versions of the scheduling cost and total resource consumption cost are discussed. We prove that these four versions can be solved in polynomial time, respectively. Some applications are also given by using the scheduling cost, which involve the makespan, total completion time, total absolute differences in completion times (TADC), and total absolute differences in waiting times (TADW). [ABSTRACT FROM AUTHOR]