Search

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]

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 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]

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]

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 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]

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 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]