Search

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]

This paper investigates single‐machine scheduling in which the processing time of a job is a function of its position in a sequence, a truncation parameter, and its resource allocation. For a convex resource consumption function, we provide a bicriteria analysis where the first is to minimize total weighted flow (completion) time, and the second is to minimize total resource consumption cost. If the weights are positional‐dependent weights, we prove that three versions of considering the two criteria can be solved in polynomial time, respectively. If the weights are job‐dependent weights, the computational complexity of the three versions of the two criteria remains an open question. To solve the problems with job‐dependent weights, we present a heuristic (an upper bound) and a branch‐and‐bound algorithm (an exact solution). [ABSTRACT FROM AUTHOR]

This article investigates the single-machine common due-window assignment problem with generalized earliness/tardiness penalties and a rate-modifying activity. Job processing times include two cases: one with constant values and another with time-dependent processing times (deterioration effect). Considering the maintenance activity, the maintenance time is a fixed constant. The goal is to determine the position of the common due window and the optimal sequence such that the following objective function is minimized: the weighted penalties for the sum of earliness and tardiness, the weighted number of early and delayed, and the weighted due-window starting time and size. It is proved that the problem can be solved in O (n 6) time, where n is the number of jobs. [ABSTRACT FROM AUTHOR]

This article addresses how to minimize total completion time on a single machine with a position-weighted learning effect. Under non-zero job release dates, a lower bound on the objective function, a number of dominance properties, and an initial solution (i.e. an NEH-based heuristic) are derived, which are used to expedite the elimination process of a branch-and-bound solution procedure. The performance of the branch-and-bound algorithm and the heuristic algorithm are evaluated on a set of randomly generated problem instances. [ABSTRACT FROM AUTHOR]

This article deals with a single-machine resource allocation scheduling problem with deteriorating jobs. Under a group technology environment, the actual processing times of jobs are a convex resource allocation function of their starting time and the amount of resource allocation. The objective is to minimize the weighted sum of makespan and resource allocation cost. For two special cases, it is proved that the problem can be solved in polynomial time. For the general case of the problem, heuristic and branch-and-bound procedures are developed to solve the problem. Computational experiments are also performed to examine the effectiveness and the efficiency of the algorithms. [ABSTRACT FROM AUTHOR]

In this article, the two-machine no-wait permutation flowshop scheduling problem with common due window assignment, learning effect and resource allocation is considered, wherein learning effect and resource allocation mean that the processing time of a job is a function of its position in a sequence and its amount of resource allocation. According to the common due window assignment method, each job is associated with a common due window, which is a decision variable. The goal is to determine the sequence of jobs, common due window starting time, due window size and resource allocation such that the linear weighted sum of job earliness, tardiness, due window size and resource cost is minimized. This article shows that the scheduling problem can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

This article deals with an integrated optimization problem of production scheduling and common due-window assignment on a single machine. The objective is to minimize the total cost, which is a weighted sum function of earliness and tardiness, due-window starting time, and due-window size, where the weights only depend on their position in a sequence (i.e. position-dependent weights). A polynomial time solution algorithm is provided for the corresponding problem. The problem can also be extended to slack due-windows assignment and general position-dependent processing times. It is proved that both these extensions remain polynomially solvable. [ABSTRACT FROM AUTHOR]

This article addresses proportionate flowshop scheduling problems with position-dependent weights wherein the weight is not related to the job but to the position in which the job is scheduled. Common and slack due date assignment models are discussed under a due date assignment framework. The goal is to determine a feasible schedule for all jobs and due dates of all jobs to minimize a total cost function wherein the objective function is of the minsum type. Optimal properties for the problems are proposed, based on which polynomial time algorithms are provided to solve these two problems optimally. [ABSTRACT FROM AUTHOR]

This article addresses the no-wait flowshop scheduling problem with simultaneous consideration of common due date assignment, convex resource allocation and learning effect in a two machine setting. The processing time of each job can be controlled by its position in a sequence and also by allocating extra resource, which is a convex function of the amount of a common continuously divisible resource allocated to the job. The objective is to determine the optimal common due date, the resource allocation and the schedule of jobs such that the total earliness, tardiness and common due date cost (the total resource consumption cost) are minimized under the constraint condition that the total resource consumption cost (the total earliness, tardiness and common due date cost) is limited. Polynomial time algorithms are developed for two versions of the problem. [ABSTRACT FROM AUTHOR]

This article addresses permutation flowshop scheduling problems with simple linear deterioration. The objectives are to minimize logarithm of the makespan, total logarithm of the completion time, total weighted logarithm of the completion time, and the sum of the quadratic job logarithms of the completion times. Approximation algorithms and their worst-case bounds are presented and analysed. Branch-and-bound algorithms are also proposed to solve the problems optimally. Computational experiments are performed to illustrate the algorithms. [ABSTRACT FROM AUTHOR]

This paper deals with a single machine bi-criterion scheduling problem with exponentially time-dependent learning effects and non-zero job release times. The goal is to minimize the weighted sum of the makespan and the total completion time. First, a branch-and-bound algorithm incorporating with some dominance properties and three lower bounds is developed for the optimal solutions. Then heuristic and particle swarm optimization algorithms are presented for near-optimal solutions. Finally, computational experiments are conducted to evaluate the performances of the proposed algorithms. Computational results indicate that the algorithms perform well in either solving the problem or efficiently generating near-optimal solutions. [ABSTRACT FROM AUTHOR]

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]

This study considers a single machine group scheduling problem with deteriorating jobs and resource allocation (controllable processing times). The objective is to have the resource availability limited within a given range, and to minimize the maximum completion time (i.e. the makespan). For two special cases, it is proved that the problem can be solved in polynomial time. For the general case, an heuristic algorithm and a branch-and-bound algorithm are proposed. Computational results show that the proposed heuristic algorithm is generally effective. [ABSTRACT FROM AUTHOR]

This article considers the no-wait flowshop scheduling with learning effect and resource allocation on two-machine. Our goal is to find the optimal resource allocations and job sequence that minimize the scheduling criterion (the total weighted resource consumption) subject to the constraint that the total weighted resource consumption (the scheduling criterion) is less than or equal to a given constant, where the schedule criteria include weighted makespan, total completion (waiting) time and total absolute differences in completion (waiting) times. We show that these two problems are polynomially solvable respectively. [ABSTRACT FROM AUTHOR]

This paper considers a single-machine scheduling problem with deteriorating jobs and convex resource allocation. We assume that the actual processing time of a job is a function of its convex resource allocation and its starting time. For the multi-objective single-machine scheduling problem, we show that the problem is polynomially solvable in O (n log n) time, where n is the total number of jobs. [ABSTRACT FROM AUTHOR]

This paper addresses resource allocation scheduling problems with CON/SLK due date assignment and job-dependent learning effects on a single machine. Two different resource consumption functions under common (denoted by CON) and slack (denoted by SLK) due date assignment are considered. The objective is to determine the optimal due dates of jobs, a sequence for jobs and resource allocation of jobs to minimize a total cost function. The optimality properties for all problems and polynomial time algorithms are proposed to solve these problems. [ABSTRACT FROM AUTHOR]

In this study we consider the problem of scheduling n jobs on m unrelated parallel processors with deterioration effect. We allow an option for performing a modifying (i.e. deteriorating) maintenance activity on each machine, i.e. the job normal processing times will be changed following this modifying maintenance activity. We need to make a decision on when to schedule the modifying maintenance activities and the sequence of jobs so as to minimize a cost function containing total completion (waiting) time, total absolute differences in completion (waiting) times, and total machine load. We show that the problem remains polynomially solvable under the proposed model. [ABSTRACT FROM AUTHOR]