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]

Single-machine due-window assignment scheduling with delivery times and variable processing times is investigated, where the variable processing time of a job means that the processing time is a function of its position in a sequence and its resource allocation. Currently, there are multiple optimization objectives for the due-window assignment problem, and there is a small amount of research on optimization problems where the window starting time, the rejected cost and the optimal scheduling are jointly required. The goal of this paper is to minimize the weighed sum of scheduling cost, resource consumption cost and outsourcing measure under the optional job outsourcing (rejection). Under two resource allocation models (i.e., linear and convex resource allocation models), the scheduling cost is the weighted sum of the number of early–tardy jobs, earliness–tardiness penalties and due-window starting time and size, where the weights are positional-dependent. The main contributions of this paper include the study and data simulation of single-machine scheduling with learning effects, delivery times and outsourcing cost. For the weighed sum of scheduling cost, resource consumption cost and outsourcing measure, we prove the polynomial solvability of the problem. Under the common and slack due-window assignments, through the theoretical analysis of the optimal solution, we reveal that four problems can be solved in O (n 6) time, where n is the number of jobs. [ABSTRACT FROM AUTHOR]

This paper studies the single-machine scheduling problem with truncated learning effect, time-dependent processing time, and past-sequence-dependent delivery time. The delivery time is the time that the job is delivered to the customer after processing is complete. The goal is to determine an optimal job schedule to minimize the total weighted completion time and maximum tardiness. In order to solve the general situation of the problem, we propose a branch-and-bound algorithm and other heuristic algorithms. Computational experiments also prove the effectiveness of the given algorithms. [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 order to increase the efficiency of production in a deteriorating environment through competition amongst the individual agents, this study explores a two-agent scheduling problem with one deterioration rate for each job, where the processing time of a job is a function of the position-dependent workload, resource allocation, and deterioration rate (the range of the deterioration rate is non-negative). The optimal processing sequence and resource allocation for the jobs are found by giving an upper bound of an agent to minimize the maximum value of earliness, tardiness and decision variable of another agent under slack due-date assignment. It is verified that the problem cannot be solved in polynomial time, for which various heuristic algorithms and a branch-and-bound algorithm are proposed to simulate the data to find a better range in the deterioration rate parameter. [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 studies the single-machine group scheduling problem with convex resource allocation and learning effect. The number of jobs in each group is different, and the corresponding common due dates are also different, where the processing time of jobs follows a convex function of resource allocation. Under common due date assignment, the objective is to minimize the weighted sum of earliness, tardiness, common due date, resource consumption, and makespan. To solve the problem, we present the heuristic, simulated annealing, and branch-and-bound algorithms. Computational experiments indicate that the proposed algorithms are effective. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the minmax single-machine scheduling problem with the slack due window, where the actual processing time of a job is the deterioration function of its starting time. The goal is to obtain the optimal schedule of the job and the related decision variables of the slack due window to minimize the linear combination cost function of the maximum earliness (tardiness) of the job and the due window. We show that this problem is solvable in O(n) time, and we carry out the numerical analysis, where $ n $ is the number of jobs. [ABSTRACT FROM AUTHOR]

In this paper, we investigate a single machine scheduling problem with a proportional job deterioration. Under release times (dates) of jobs, the objective is to minimize the total weighted completion time. For the general condition, some dominance properties, a lower bound and an upper bound are given, then a branch-and-bound algorithm is proposed. In addition, some meta-heuristic algorithms (including the tabu search ( T S ), simulated annealing ( S A ) and heuristic ( N E H ) algorithms) are proposed. Finally, experimental results are provided to compare the branch-and-bound algorithm and another three algorithms, which indicate that the branch-and-bound algorithm can solve instances of 40 jobs within a reasonable time and that the N E H and S A are more accurate than the T S . [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]

Green scheduling that aims to enhance efficiency by optimizing resource allocation and job sequencing concurrently has gained growing academic attention. To tackle such problems with the consideration of scheduling and resource allocation, this paper considers a single-machine group scheduling problem with common/slack due-date assignment and a controllable processing time. The objective is to decide the optimized schedule of the group/job sequence, resource allocation, and due-date assignment. To solve the generalized case, this paper proves several optimal properties and presents a branch-and-bound algorithm and heuristic algorithms. Numerical experiments show that the branch-and-bound algorithm is efficient and the heuristic algorithm developed based on the analytical properties outruns the tabu search. [ABSTRACT FROM AUTHOR]

This paper addresses the single-machine scheduling problem with learning effects and exponential past-sequence-dependent delivery times. The objective is to determine an optimal job schedule such that total weighted completion time and maximum tardiness are minimized. To solve the general case of the problem, we propose the heuristic, simulated annealing and branch-and-bound algorithms. The computational experiment are also conducted to show that the algorithms perform effectively. [ABSTRACT FROM AUTHOR]

In this paper, we study a single-machine green scheduling problem with learning effects and past-sequence-dependent delivery times. The problem can be properly applied to tackle green manufacturing where production and delivery time are variable and highly subject to process-reengineering. Our goal is to determine the optimal sequence such that total weighted completion time and maximum tardiness are minimized. For the general case, we provide the analysis procedure of lower bound, and also propose the heuristic and branch-and-bound algorithms. Furthermore, computational experiments are conducted to demonstrate the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

In practical problems, in addition to the processing time of the job, the impact of the time required for delivering the service to customers on the cost is also considered, i.e., delivery time, where the job processing time is a simple linear function of its starting time. This paper considers the impact of past-sequence-dependent delivery times (which can be referred to as p s d d t ) on the studied objectives in three types of due windows (common, slack and different due windows). This serves to minimize the weighted sum of earliness, tardiness, starting time and size of due window, where the weights (coefficients) are related to the location. Through the theoretical analysis of the optimal solution, it is found that these three problems can be solved in time O (N log N) , respectively, where N is the number of jobs. [ABSTRACT FROM AUTHOR]

In this paper, the single-machine scheduling problems under the common and slack due date assignments are studied, where the actual processing time of the job needs to consider some factors, such as convex resource allocation, maintenance activity, and learning effects. The goal of this study is to find the optimal sequence, maintenance activity location, resource allocation and common due date (flow allowance). The objective function is (1) to minimize the sum of scheduling cost (including the weighted sum of earliness, tardiness and common due date (flow allowance), where the weights are position-dependent weights) and resource consumption cost, and (2) to minimize the scheduling cost under the resource consumption cost which is bounded. We prove that these problems can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

In classical schedule problems, the actual processing time of a job is a fixed constant, but in the actual production process, the processing time of a job is affected by a variety of factors, two of which are the learning effect and resource allocation. In this paper, single-machine scheduling problems with resource allocation and a time-dependent learning effect are investigated. The actual processing time of a job depends on the sum of normal processing times of previous jobs and the allocation of non-renewable resources. With the convex resource consumption function, the goal is to determine the optimal schedule and optimal resource allocation. Three problems arising from two criteria (i.e., the total resource consumption cost and the scheduling cost) are studied. For some special cases of the problems, we prove that they can be solved in polynomial time. More generally, we propose some accurate and intelligent algorithms to solve these problems. [ABSTRACT FROM AUTHOR]

In enterprise management, there are often multiple agents competing for the same products to reduce production cost. On this basis, this paper investigates a two-agent slack due-date single-machine scheduling problem with deteriorating jobs, where the processing time of a job is extended as a function of position-dependent workload, resource allocation and a common deterioration rate. The goal is to find the optimal sequence and resource allocation that minimizes the maximal value of earliness, tardiness, and decision variables of one agent subject to an upper bound on cost value of the second agent. Through theoretical analysis, a polynomial time algorithm with O (N 3) time is proposed for the problem, where N is the maximum number of jobs between the two agents. [ABSTRACT FROM AUTHOR]

This paper investigates the single-machine resource allocation scheduling problem with learning effects and group technology. The objective is to determine the optimal job and group schedules, and resource allocations such that total completion time is minimized subject to limited resource availability. For some special cases, we show that the problem remains polynomially solvable. For general case of the problem, we propose the heuristic algorithm, tabu search algorithm and branch-and-bound algorithm. Numerical experiments are tested to evaluate the performance of the heuristic and branch-and-bound algorithms. [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]

This paper investigates single-machine scheduling with a deteriorating maintenance activity, where the processing time of a job depends on whether it is handled before or after the maintenance activity. Under common and slack due date assignments, the aim is to find the optimal job schedule, position of the maintenance activity, and optimal value of the common due date (flow-allowance) so that the linear weighted sum of earliness, tardiness and common due date (flow-allowance) value is minimized, where the weights are location-dependent (position-dependent) weights. Through a series of optimal properties, a polynomial time algorithm is proposed and it is then proven that the problem is polynomially solvable. [ABSTRACT FROM AUTHOR]

We study the problem of two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times. Under the condition of the due-date assignment with common flow allowance (i.e. slack (SLK) due-date assignment), we provide a bi-criteria analysis where the first criterion is to minimise the scheduling criteria (i.e. the weighted sum of earliness, tardiness and flow allowance costs), and the second criterion is to minimise the resource consumption cost (i.e. the weighted sum of resource consumption cost). The objective is to determine the optimal job sequence, resource allocations and common (flow allowance) slack time that minimise the three different versions of the two criteria. We prove that these problems can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

Under just-in-time production, this paper studies a single machine common due-window (denoted by CONW) assignment scheduling problem with position-dependent weights and resource allocations. A job's actual processing time can be determined by the resource assigned to the job. A resource allocation model is divided into linear and convex resource allocations. Under the linear and convex resource allocation models, our goal is to find an optimal due-window location, job sequence and resource allocation. We prove that the weighted sum of scheduling cost (including general earliness–tardiness penalties with positional-dependent weights) and resource consumption cost minimization is polynomially solvable. In addition, under the convex resource allocation, we show that scheduling (resp. resource consumption) cost minimization is solvable in polynomial time subject to the resource consumption (resp. scheduling) cost being bounded. [ABSTRACT FROM AUTHOR]

This paper studies the slack due-window assignment scheduling problem with deterioration effects and a deterioration maintenance activity on a single-machine. The machine deteriorates during the machining process, and at a certain moment performs a deterioration maintenance activity, that is, the duration time of the maintenance activity is a linear function of the maintenance starting time. It is needed to make a decision on when to schedule the deteriorating maintenance activity, the optimal common flow allowances and the sequence of jobs to minimize the weighted penalties for the sum of earliness and tardiness, weighted number of early and delayed, and weighted due-window starting time and size. This paper proposes a polynomial time algorithm to solve this problem. [ABSTRACT FROM AUTHOR]

We focus on a single-machine scheduling problem with common and slack due-window assignment methods. Both the job sequence and due-windows are decision variables to be determined by the decision maker. We consider the following performance criterion: the total weighted number of early and late jobs plus the total weighted of earliness, tardiness and due-window assignment cost, where the weights depend on the position in which a job is scheduled. Some properties are established, and it is shown that the problem can be solved in O (n 5) time, where n is the number of jobs. The extensions of the model are to cases of general position-dependent processing times and time-dependent processing times. [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]

This paper studies a single-machine problem with resource allocation ( R A ) and deteriorating effect ( D E ). Under group technology ( G T ) and limited resource availability, our goal is to determine the schedules of groups and jobs within each group such that the total completion time is minimized. For three special cases, polynomial time algorithms are given. For a general case, a heuristic, a tabu search algorithm, and an exact (i.e., branch-and-bound) algorithm are proposed to solve this problem. [ABSTRACT FROM AUTHOR]