Search

We consider a two-machine no-wait permutation flow shop common due date assignment scheduling problem where the processing time of a job is given as a function of its position in the sequence and its amount of resource allocated to this job. The common due date (CON) assignment method means that all the jobs are given a common due date. We need to make a decision on the common due date, resource allocation and the sequence of jobs to minimise total earliness, tardiness, common due date cost and total resource cost. We show that the problem remains polynomially solvable under the proposed model. [ABSTRACT FROM AUTHOR]

This paper considers a single-machine scheduling problem involving convex resource-dependent processing times and due-window assignment simultaneously. The goal is to minimise the total resource consumption cost under the constraint that the schedule cost involving earliness, tardiness, window location, window size and makespan does not exceed a given limit for two popular due window assignment methods: the common flow allowance (slack) due window assignment method (referred to SLKW) and the common due window assignment method (referred to CONW). We show that the problem can be solved in polynomial time. Some extensions of the problem are also given. [ABSTRACT FROM PUBLISHER]

We study resource allocation scheduling with job-dependent learning effect on a single machine with or without due date assignment considerations. For a convex resource processing time function, we provide a polynomial time algorithm to find the optimal job sequence, and resource allocations that minimise the schedule criterion (the total compression cost) subject to the constraint that the total compression cost (the schedule criterion) is less than or equal to a fixed amount. [ABSTRACT FROM PUBLISHER]

The permutation flow shop problems with truncated exponential sum of logarithm processing times based and position‐based learning effects are considered in this study. The objective is to minimize makespan and total weighted completion time, respectively. Several heuristics and a branch‐and‐bound algorithm are proposed in this paper. The tight worst‐case bounds of some simple heuristics are also given. Numerical experiments are tested to evaluate the performance of the heuristics and branch‐and‐bound algorithm. [ABSTRACT FROM AUTHOR]

We investigate a group scheduling problem with shortening job processing times on a single machine in which the shortening is proportional-linear shortening and the setup time of a group is fixed. For the maximum completion time (i.e. the makespan) minimization problem with ready times, we show that the general case of the problem can be solved in polynomial time if the number of groups is a given constant. We also prove that some special cases of the problem can be optimally solved by a lower order algorithm respectively. [ABSTRACT FROM AUTHOR]

This article considered the single machine scheduling with controllable processing time (resource allocation) and deterioration effect concurrently. It discussed the minimization of three objectives, which involve the weighted sum of the makespan and the total resource consumption cost, the total resource consumption cost under the condition that the makespan (total flow time) is restricted to a fixed constant and the optimal resource allocation and the optimal job sequence is what we need to make decision. Considering the makespan constraint, it proved that these problems can be solved in polynomial time. A special case of the last problem can be solved in polynomial time with respect to the total flow time constraint. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of unrelated parallel machine scheduling with controllable processing times and deteriorating maintenance activity. The jobs are nonresumable. The processing time of each job is a linear function of the amount of a continuously divisible resource allocated to the job. During the planning horizon, there is at most one maintenance activity scheduled on each machine. Additionally, if the starting time of maintenance activity is delayed, the length of the maintenance activity required to perform will increase. Considering the total completion times of all jobs, the impact of maintenance activity in the form of the variation in machine load and the amounts of compression, we need to determine the job sequence on each machine, the location of maintenance activities and processing time compression of each job simultaneously. Accordingly, a polynomial time solution to the problem is provided. [ABSTRACT FROM AUTHOR]

This paper considers single-machine scheduling with learning effect, deteriorating jobs and convex resource dependent processing times, i.e., the processing time of a job is a function of its starting time, its position in a sequence and its convex resource allocation. The objective is to find the optimal sequence of jobs and the optimal convex resource allocation separately to minimize a cost function containing makespan, total completion (waiting) time, total absolute differences in completion (waiting) times and total resource cost. It is proved that the problem can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

The paper is devoted to some single-machine scheduling problems with variable job processing times. The objectives are to minimize the makespan (i.e., the maximum completion time of all jobs), and to minimize the total completion time. For some special cases, we show that these problems can be solved in polynomial time. For some another special cases of the makespan and the total completion time minimization problems, we prove that an optimal schedule has an V-shape property in terms of processing times. We also propose a heuristic algorithm by utilizing the V-shape property. [ABSTRACT FROM AUTHOR]

In this study we consider unrelated parallel machines scheduling problems with learning effect and deteriorating jobs, in which the actual processing time of a job is a function of joint time-dependent deterioration and position-dependent learning. The objective is to determine the jobs assigned to corresponding each machine and the corresponding optimal schedule to minimize a cost function containing total completion (waiting) time, total absolute differences in completion (waiting) times and total machine load. If the number of machines is a given constant, we show that the problems can be solved in polynomial time under the time-dependent deterioration and position-dependent learning model. [ABSTRACT FROM AUTHOR]

This paper considers a group scheduling problem with two ordered criteria where both setup times and job-processing times are increasing functions of their starting times. It is assumed that the jobs be classified into several groups and the jobs of the same group have to be processed contiguously. We consider two objectives where the primary criterion is the total weighted completion time and the secondary criterion is the maximum cost. A polynomial time algorithm is presented to solve this bicriterion group scheduling problem with deteriorating setup times and job-processing times. This algorithm can also solve single-machine group scheduling problems with deteriorating setup times and job-processing times in several ordered maximum cost and arbitrary precedence. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we investigate a single machine scheduling problem with decreasing time-dependent processing times and group technology assumption. By the decreasing time-dependent processing times and group technology assumption, we mean that the group setup times and job processing times are both decreasing linear functions of their starting times. We want to minimize the makespan subject to release dates. We show that the problem can be solved in polynomial time. [Copyright &y& Elsevier]

We study a single-machine earliness-tardiness scheduling problem with due date assignment, in which the processing time of a job is a function of its starting time and its resource allocation. We analyze the problem with two different processing time functions and three different due date assignment methods. The goal is to minimize an integrated objective function, which includes earliness, tardiness, due date assignment, and total resource consumption costs. For each combination of due date assignment method and processing time function, we provide a polynomial-time algorithm to find the optimal job sequence, due date values, and resource allocations. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we consider single-machine scheduling problems with position-dependent processing times, i.e., jobs whose processing times are an increasing or decreasing function of their positions in a processing sequence. In addition, the jobs are related by parallel chains and a series–parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan polynomial algorithms exist. [Copyright &y& Elsevier]

The single-machine slack due date scheduling problem with deteriorating jobs is researched, where the deterioration effect means that the actual processing time of jobs is defined as increasing function of their starting time and the deteriorating rates of all jobs are identical, and due date of the job is equal to its actual processing time plus the common slack time. The objective is to determine the optimal scheduling and the common slack time simultaneously to minimize the sum of earliness, tardiness and common slack. time. It is proved that the problem can be transformed into the product of two vectors by the operations research method, thus can be solved in polynomial time, and the optimal algorithm to solve the problem is given. [ABSTRACT FROM AUTHOR]

We study a single machine slack due date assignment (usually referred to as SLK) scheduling problem with deteriorating jobs and a rate-modifying activity. The deterioration effect manifest such that the job processing time is a function of its starting time in a sequence. The rate-modifying activity is an activity that changes the processing rate of machine, i.e., the machine performs a rate-modifying activity. Hence the actual processing time of a job is a variable, which depends not only on its starting time in a sequence but also on whether it is scheduled before or after a rate-modifying activity. The goal is to schedule the rate-modifying activity, the optimal common flow allowance and the sequence of jobs to minimize the total earliness, the total tardiness and the common flow allowance cost. We show that the problem remains polynomially solvable under the proposed model. [ABSTRACT FROM AUTHOR]