Search

In this paper we consider single-machine scheduling problems with group technology, where the group setup times are general linear functions of their starting times and the jobs in the same group have general truncated learning effects. The objective is to minimize the makespan and total completion time, respectively. We show that the makespan minimization remains polynomially solvable. For the total completion time minimization, optimal properties are presented and then we introduce some heuristic algorithms and a branch-and-bound algorithm. [ABSTRACT FROM AUTHOR] more...

This paper discusses the single-machine scheduling problems with deteriorating jobs and past-sequence-dependent delivery times. Under the general deterioration function, the objective is to determine an optimal schedule for the job that minimizes the makespan, and the total weighted completion time. We demonstrate that the makespan minimization is polynomially solvable. For the total weighted completion time, this problem is NP-hard, to solve this problem, we provide the branch-and-bound algorithm and some heuristic algorithms. [ABSTRACT FROM AUTHOR] more...

In this paper, we study scheduling with step-learning, i.e., a setting where the processing times of the jobs started after their job-dependent learning-dates are reduced. The goal is to minimize makespan on a single machine. We focus first on the case that idle times between consecutive jobs are not allowed. We prove that the problem is NP-hard, implying that no polynomial-time solution exists and, consequently, propose a pseudo-polynomial time dynamic programming algorithm. An extensive numerical study is provided to examine the running time of the algorithm with different learning-dates and job processing time ranges. The special case of a common learning-date for all the jobs is also studied, and a (more efficient) pseudo-polynomial dynamic programming is introduced and tested numerically. In the last part of the paper, the more complicated setting in which idle times are allowed is studied. An appropriate dynamic programming is introduced and tested as well. [ABSTRACT FROM AUTHOR] more...

This paper develops an economic production quantity model for a single-machine multiproduct imperfect production system with a set of alternative assumptions. The system under study can produce different types of products using a single machine. Fresh production and rework of imperfect items are performed on the same production line. The model is developed with different operational possibilities on imperfect items. The model aims to investigate the effects of continuous supply of all products throughout a planning period, unequal production cycles, and removal of idle inventory downtimes. A constrained nonlinear mathematical model is derived for the system. The model is optimized using the logarithmic barrier method that uses Newton's iterative process to calculate the optimal value in each stage. A numerical example and sensitivity analysis are presented to validate the proposed model and optimization method. Some managerial applications of the model are explained. [ABSTRACT FROM AUTHOR] more...

We study several competitive two-agent scheduling problems with release dates and preemption on a single machine, where the scheduling criterion of the first agent is regular and of the sum-form and the scheduling criterion of the second criterion is regular and of the max-form or the weighted number of tardy jobs. Two variants of the problems are investigated. One is the restricted version, in which the goal is to find a feasible schedule so that the objective value of the first agent is minimized subject to the restriction that the objective value of the second agent does not exceed a given threshold value. The other one is the Pareto version, in which the goal is to find all the Pareto-optimal points and their corresponding Pareto-optimal schedules. We design polynomial-time and pseudo-polynomial-time algorithms for each of the considered problems. [ABSTRACT FROM AUTHOR] more...

In the literature on multi-scenario scheduling problems, it is assumed that (i) each scenario defines a different possible realization of the job's parameters; and (ii) the value of each parameter is arbitrary for any job in any scenario. Under these assumptions many multi-scenario scheduling problems have been proven to be NP -hard. We study a special case of this set of problems, in which there is an agreeable condition between scenarios on the processing-time parameters. Accordingly, the processing time of job J j under scenario s i is at most its value under scenario s i + 1 , for i = 1 , ... q - 1 , where q is the number of different possible scenarios. We focus on three classical scheduling problems for which the single-scenario case is solvable in polynomial time, while the multi-scenario case is NP -hard, even when there are only two scenarios. The three scheduling problems consist of minimizing either the total completion time or the number of tardy jobs on a single machine, and minimizing the makespan in a two-machine flow-shop system. We show that the multi-scenario version of all three problems remains NP -hard even when processing times are agreeable and there are only two scenarios. We also show that for a more specific structure of job processing times two out of the three problems become easy to solve, while the complexity status of the third remains open for future research. [ABSTRACT FROM AUTHOR] more...

This article studies scheduling problems with past-sequence-dependent delivery times (denoted by psddt) on a single-machine, i.e., the delivery time of a job depends on its waiting time of processing. We prove that the total (discounted) weighted completion time minimization can be solved in O (n log n) time, where n is the number of jobs, and the weight is a position-dependent weight. For common (denoted by con) and slack (denoted by slk) due-date assignment and position-dependent weights (denoted by pdw), we prove that an objective cost minimization is solvable in O (n log n) time. The model (i.e., psddt and pdw) can also be extended to position-dependent (time-dependent) processing times. [ABSTRACT FROM AUTHOR] more...

Research on non-regular performance measures is at best scarce in the deterministic machine scheduling literature with machine unavailability constraints. Moreover, almost all existing works in this area assume either that processing on jobs interrupted by an interval of machine unavailability may be resumed without any additional setup/processing or that all prior processing is lost. In this work, we intend to partially fill these gaps by studying the problem of scheduling a single machine so as to minimize the total deviation of the job completion times from an unrestrictive common due date when one or several fixed intervals of unavailability are present in the planning horizon. We also put serious effort into investigating models with semi-resumable jobs so that processing on a job interrupted by an interval of machine unavailability may later be resumed at the expense of some extra processing time. The conventional assumptions regarding resumability are also taken into account. Several interesting cases are identified and explored, depending on the resumability scheme and the location of the interval of machine unavailability with respect to the common due date. The focus of analysis is on structural properties and drawing the boundary between polynomially solvable and NP -complete cases. Pseudo-polynomial dynamic programming algorithms are devised for NP -complete variants in the ordinary sense. [ABSTRACT FROM AUTHOR] more...

We address cumulative deterioration scheduling in which two agents compete to perform their respective jobs on a single machine. By cumulative deterioration we mean that the actual processing time of any job of the two agents is a linear increasing function of the total normal processing times of already processed jobs. Each agent desires to optimize some scheduling criterion that depends on the completion times of its own jobs only. We study several scheduling problems arising from different combinations of some regular scheduling criteria, including the maximum cost (embracing lateness and makespan as its special cases), the total completion time, and the (weighted) number of tardy jobs. The aim is to find an optimal schedule that minimizes the objective value of one agent while maintaining the objective value of the other agent not exceeding a fixed upper bound. For each problem under study, we design either a polynomial-time or a pseudo-polynomial-time algorithm to solve it. [ABSTRACT FROM AUTHOR] more...

This paper introduces the serial batching scheduling problems with position-based learning effect, where the actual job processing time is a function of its position. Two scheduling problems respectively for single-machine and parallel-machine are studied, and in each problem the objectives of minimizing maximum earliness and total number of tardy jobs are both considered respectively. In the proposed scheduling models, all jobs are first partitioned into serial batches, and then all batches are processed on the serial-batching machine. We take some practical production features into consideration, i.e., setup time before processing each batch increases with the time, regarded as time-dependent setup time, and we formalize it as a linear function of its starting time. Under the single-machine scheduling setting, structural properties are derived for the problems with the objectives of minimizing maximum earliness and number of tardy jobs respectively, based on which optimization algorithms are developed to solve them. Under the parallel-machine scheduling setting, a hybrid VNS-GSA algorithm combining variable neighborhood search (VNS) and gravitational search algorithm (GSA) is proposed to solve the problems with these two objectives respectively, and the effectiveness and efficiency of the proposed VNS-GSA are demonstrated and compared with the algorithms of GSA, VNS, and simulated annealing (SA). This paper demonstrates that the consideration of different objectives leads to various optimal decisions on jobs assignment, jobs batching, and batches sequencing, which generates a new insight to investigate batching scheduling problems with learning effect under single-machine and parallel-machine settings. [ABSTRACT FROM AUTHOR] more...

This paper deals with a single machine common due window assignment resource allocation scheduling problem with job-dependent learning effect. The objective is to find the due window starting time, a due window size, resource allocation and a job schedule such that total resource consumption cost is minimized subject to a cost function associated with the window location, window size, earliness, tardiness and makespan is less than or equal to a fixed constant number. We show that the problem can be solved in polynomial time. Some extensions of the problem are also given. [ABSTRACT FROM AUTHOR] more...

This article considers the single-machine serial-batching scheduling problem with a machine availability constraint, position-dependent processing time, and time-dependent set-up time. The objective of this problem is to make the decision of batching jobs and sequencing batches to minimize the makespan. To solve the problem, three cases of machine non-availability periods are considered, and the structural properties of the optimal solution are derived for each case. Based on these structural properties, an optimization algorithm is developed and an example is proposed to illustrate this algorithm. [ABSTRACT FROM AUTHOR] more...

In this paper, two-agent scheduling problems are presented. The different agents share a common processing resource, and each agent wants to minimize a cost function depending on its jobs only. The objective functions we consider are the total weighted late work and the maximum cost. The problem is to find a schedule that minimizes the objective function of agent A, while keeping the objective function of agent B cannot exceed a given bound U. Some different scenarios are presented by depending on the objective function of each agent. We address the complexity of those problems, and present the optimal polynomial time algorithms or pseudo-polynomial time algorithm to solve the scheduling problems, respectively. [ABSTRACT FROM AUTHOR] more...

This paper deals with serial-batching scheduling problems with the effects of deterioration and learning, where time-dependent setup time is also considered. In the proposed scheduling models, all jobs are first partitioned into serial batches, and then all batches are processed on a single serial-batching machine. The actual job processing time is a function of its starting time and position. In addition, a setup time is required when a new batch is processed, and the setup time of the batches is time-dependent, i.e., it is a linear function of its starting time. Structural properties are derived for the problems of minimizing the makespan, the number of tardy jobs, and the maximum earliness. Then, three optimization algorithms are developed to solve them, respectively. [ABSTRACT FROM AUTHOR] more...

We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a single machine. A setup time is needed for a job if it is the first job to be processed on the machine or its processing on the machine follows a job that belongs to another family. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The aim is to find a schedule for all the jobs of the two agents that minimizes the objective of one agent while keeping the objective of the other agent being bounded by a fixed value $$Q$$ . Polynomial-time and pseudo-polynomial-time algorithms are designed to solve the problem involving various combinations of regular scheduling objective functions. [ABSTRACT FROM AUTHOR] more...

In just-in-time production, meeting due dates is one of the most important goals. Motivated by a scenario of just-in-time production, this paper considers the single-machine scheduling problem with release times and common due date assignment. The objective is to determine the optimal due date and schedule simultaneously to minimize a cost function that includes the weighted number of tardy jobs and the due date assignment cost. We show that the problem is NP-hard in the ordinary sense, and propose a dynamic programming algorithm and a fully polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR] more...

In the survey scheduling theory, if a surgical patient is regarded as a job waiting to be processed, and the anesthesiologist care unit nurses as machines that are needed before the survey. Due to the lack of operating rooms or the accidental extension of operation time, the patients will have a longer wait time, and can not do operation following the effects of the anaesthetic. The patient needs to be re-anesthesia so that the effects are required to undergo surgery. But this will cause operation time prolonged. Based on the performance of medical procedures under deteriorating health conditions, this paper presents a deterministic approach to schedule patients in surgery scheduling problems with the deferred parameter. We take the patients as jobs. By the deferred deteriorating effect, it means that the actual processing time of a job is a function of its starting time and a control parameter. We prove that the classical SPT (the shortest processing time) rule remains optimal when we minimize the makespan or the total completion time. For problems of minimizing the total weighted completion time and the maximum lateness, we present heuristic sequencing rules and analyze the worst-case bounds for performance ratios. We also show that these heuristic rules can be optimal under some agreeable conditions between the normal processing times and job due dates or weights. [ABSTRACT FROM AUTHOR] more...

Competitive multi-agent scheduling has attracted increasingly more and more researchers' attention recently. Inspired by the observation that a machine may not be always available during the whole planning horizon, we study a new category of scheduling problems where competitive two-agent scheduling and flexible periodic maintenance are considered simultaneously. As a start of this new topic, we focus our attention on establishing mathematical programming models for some of these scheduling problems. Specifically, we first present a framework for the general problem, and then construct various constraint blocks, which include common constraint block, constraint block for the relationship between start times and completion times of the jobs, constraint block for the relationship between the jobs and the maintenance activities, constraint block for various regular objective functions of the two agents, constraint block for the ranges of variables, and constraint block for the other constraint factors. One can establish mathematical programming models for at least 512 scheduling scenarios of this category easily based on these constraint blocks. The work presented in this paper is extremely useful for the production managers and software developers who are seeking for optimization models to generate optimal schedules for their problems. [ABSTRACT FROM AUTHOR] more...

Scheduling with deterioration effects has been widely investigated in the past two decades. In realistic situations, the deterioration effect might accelerate, especially in the food manufacturing industry. In this paper we propose a scheduling model with an accelerating deterioration effect. We show that the single-machine problems under the model to minimize the makespan, total completion time, total weighted completion time, maximum lateness, maximum tardiness, and total tardiness remain polynomially solvable. [ABSTRACT FROM AUTHOR] more...

In this paper, we consider single-machine scheduling problems with deteriorating jobs and resource allocation in a group technology environment. In the proposed model of this paper the actual processing time of a job depend on its starting time and the amount of resource allocated to it, and the actual setup time of a group depend on its starting time and the amount of resource allocated. Deterioration effect and two resource allocation functions are examined for minimizing the weighted sum of makespan and total resource cost. For the linear resource allocation function and the convex resource allocation function, we show that the problem remains polynomially solvable under certain conditions. [ABSTRACT FROM AUTHOR] more...

In this paper, we consider a single-machine earliness-tardiness scheduling problem with due-date assignment, in which the processing time of a job is a function of its position in a sequence and its resource allocation. The due date assignment methods studied include the common due date, and the slack due date, which reflects equal waiting time allowance for the jobs. 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 that minimize an integrated objective function, which includes earliness, tardiness, due date assignment, and total resource consumption costs. [ABSTRACT FROM AUTHOR] more...

We study inherent structural properties of a strongly NP-hard problem of scheduling $$n$$ jobs with release times and due dates on a single machine to minimize the number of late jobs. Our study leads to two polynomial-time algorithms. The first algorithm with the time complexity $$O(n^3\log n)$$ solves the problem if during its execution no job with some special property occurs. The second algorithm solves the version of the problem when all jobs have the same length. The time complexity of the latter algorithm is $$O(n^2\log n)$$, which is an improvement over the earlier known algorithm with the time complexity $$O(n^5)$$. [ABSTRACT FROM AUTHOR] more...

In scheduling problems with learning effects, most research assumes that processing times are deterministic. This paper studies a single-machine scheduling problem with a position-based learning effect and fuzzy processing times where the objective is to minimize the makespan. The position-based learning effect of a job is assumed to be a function of its position. The processing times are considered to be triangular fuzzy numbers. Two different polynomial-time algorithms are developed for the problem. The first solution methodology is based on the fuzzy chance-constrained programming, whereas the second is based on a method to rank fuzzy numbers. Computational experiments are then conducted in order to evaluate the performance of the algorithms. [ABSTRACT FROM AUTHOR] more...

Traditionally, job processing times are assumed to be known and fixed; however, there are many situations in which a job that is processed later consumes more time than the same job when it is processed earlier. This is known as deteriorating jobs scheduling in the literature. Most of the research in deteriorating jobs scheduling assumes that the actual job processing time is a linear function of its starting time. Thus, the actual job processing times might increase significantly if the number of jobs or the job sizes increase. Motivated by this limitation, this paper addresses a new deterioration model where the actual job processing time is a function of the logarithm of the job processing times already processed. Under the proposed model, we provide the optimal solutions for some single-machine problems. [ABSTRACT FROM AUTHOR] more...

This paper is the first attempt to successfully design efficient approximation algorithms for the single-machine weighted flow-time minimization problem when jobs have different release dates and weights equal to their processing times under the assumption that one job is fixed (i.e., the machine is unavailable during a fixed interval corresponding to the fixed job). Our work is motivated by an interesting algorithmic application to the generation of valid inequalities in a branch-and-cut method. Our analysis shows that the trivial FIFO sequence can lead to an arbitrary large worst-case performance bound. Hence, we modify this sequence so that a new 2-approximation solution can be obtained for every instance and we prove the tightness of this bound. Then, we propose a fully polynomial-time approximation algorithm with efficient running time for the considered problem. Especially, the complexity of our algorithm is strongly polynomial. [ABSTRACT FROM AUTHOR] more...

In this paper, we presented a scheduling model in which the deteriorating jobs and the setup times are considered at the same time. Under the proposed model, the actual job processing time is a general function of the processing times of jobs already processed and its scheduled position, while the setup time is past-sequence-dependent. We provided the optimal schedules for some single-machine scheduling problems. [ABSTRACT FROM AUTHOR] more...

This paper considers single-machine scheduling problems with group technology (GT). We consider the case of group setup times and job processing times are a decreasing function of their starting time. We first prove that the makespan minimization problem remains polynomially solvable under the general decreasing linear deterioration. We then prove that the total weighted completion time minimization problem remains polynomially solvable under the proportional decreasing linear deterioration. [ABSTRACT FROM AUTHOR] more...

This paper considers a single-machine scheduling model with past-sequence-dependent setup times and a general learning effect. It develops a general model with setup times and learning effect considerations where the actual processing time of a job is not only a function of the total actual processing time of the jobs already processed, but also a function of the job’s scheduled position. The paper shows that the single-machine scheduling problems to minimize the makespan and the sum of the kth power of completion times are polynomially solvable under the proposed model. It further shows that the problems to minimize the total weighted completion time and the maximum lateness are polynomially solvable under certain conditions. [ABSTRACT FROM AUTHOR] more...

We consider a single-machine scheduling problem with deteriorating jobs in which the due dates are determined by the equal slack (SLK) method. By a deteriorating job, we mean that the job’s processing time is an increasing function of its starting time. We model job deterioration as a function that is proportional to a linear function of time. The objective is to minimize the total weighted earliness penalty subject to no tardy jobs. We prove that two special cases of the problem remain polynomially solvable. The first case is the problem with equally weighted monotonous penalty objective function and the other case is the problem with weighted linear penalty objective function. [ABSTRACT FROM AUTHOR] more...

In this paper, we consider two single-machine scheduling problems with the effect of deterioration and learning. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. For the following two objective functions, the weighted sum of completion times and the maximum lateness, this paper gives two heuristics according to the corresponding problems without learning effect. This paper also gives the worst-case error bound for the heuristics and provides computational results to evaluate the performance of the heuristics. [ABSTRACT FROM AUTHOR] more...

We consider a single-machine scheduling problem with deteriorating jobs in which the due dates are determined by the equal slack method. In this model, the processing time of a job is defined as a simple linear function of its starting time. The objective is to minimize the total weighted earliness penalty subject to no tardy jobs. We prove that two special cases of the problem remain polynomially solvable. The first case is the problem with equally weighted monotonous penalty objective function and the other case is the problem with weighted linear penalty objective function. [ABSTRACT FROM AUTHOR] more...

The paper deals with the single-machine scheduling problem with a sum-of-processing-time- based learning effect and deteriorating jobs. By the effects of sum-of-processing-time-based learning and deterioration, we mean that the processing time of a job is defined by function of its starting time and total normal processing time of jobs in front of it in the sequence. It is shown that, even with the introduction of the effects of sum-of-processing-time-based learning and deterioration to job processing times, the single-machine makespan minimization problem remains polynomially solvable. [ABSTRACT FROM AUTHOR] more...

Machine scheduling problems with deteriorating jobs have received increasing attention in recent years, mostly focusing on the linear deterioration models. However, if certain maintenance procedures fail to be completed prior to a prespecified deadline, jobs will require extra time for successful accomplishment in some situations. Therefore, this paper addresses a single-machine problem where the objective is to minimize the makespan under the piecewise linear deterioration model. A branch-and-bound algorithm and two heuristic algorithms are provided to search for the optimal solution and near-optimal solutions, respectively. Computational results are also presented to evaluate the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR] more...

In this paper, we consider the single-machine scheduling problem with a deteriorating function. By the deteriorating function, we mean that the actual job processing time is a function of jobs already processed. We show that the total completion time minimization problem for a ≥ 1 remains polynomially solvable under the proposed model, where a denotes the deterioration rate. For the case of 0 < a < 1, we show that an optimal schedule of the total completion time minimization problem is V-shaped with respect to normal job processing times. We use the classical smallest processing time first rule as a heuristic algorithm for the case of 0 < a < 1 and analyze its worst-case bound. [ABSTRACT FROM AUTHOR] more...

This paper considers a single-machine scheduling problem with both deterioration and learning effects. The objectives are to respectively minimize the makespan, the total completion times, the sum of weighted completion times, the sum of the kth power of the job completion times, the maximum lateness, the total absolute differences in completion times and the sum of earliness, tardiness and common due-date penalties. Several polynomial time algorithms are proposed to optimally solve the problem with the above objectives. [ABSTRACT FROM AUTHOR] more...

Recently, deteriorating job scheduling problems have received increasing attention. However, the majority of the research assumes that the actual job processing time is a function of its starting time. In this note, we develop a new deterioration model where the actual job processing time is a function of jobs already processed. We show that the single-machine makespan problem remains polynomially solvable under the proposed model. [ABSTRACT FROM AUTHOR] more...

This paper investigates single-machine scheduling problems with deteriorating jobs and the group technology (GT) assumption. By deteriorating jobs and the group technology assumption, we mean that the group setup times and job processing times are both increasing functions of their starting times, i.e., the group setup times and job processing times are both described by a function which is proportional to a linear function of time. The two objectives of scheduling problems are to minimize the makespan and the total weighted completion time, respectively. We show that these problems remain solvable in polynomial time when deterioration and group technology are considered simultaneously. [ABSTRACT FROM AUTHOR] more...

In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided. [ABSTRACT FROM AUTHOR] more...

In this paper we consider a single-machine scheduling model with deteriorating jobs and simultaneous learning, and we introduce polynomial solutions for single machine makespan minimization, total flow times minimization and maximum lateness minimization corresponding to the first and second special cases of our model under some agreeable conditions. However, corresponding to the third special case of our model, we show that the optimal schedules may be different from those of the classical version for the above objective functions. [ABSTRACT FROM AUTHOR] more...

Two preemptive single-machine bicriteria scheduling problems with release dates and deadlines are considered in this paper. Each criterion is formulated as a maximum cost. In the first problem the cost of both criteria depends on the completion time of the tasks. This problem can be solved by enumerating all the Pareto optimal points with an approach proposed by Hoogeveen (1996) for the nonpreemptive problem without release dates. In the second problem, the costs of one criterion are dependent on the completion times of the tasks and the costs of the other criterion are dependent on the scan limes. This problem is more difficult but an efficient algorithm is proposed for a sub-problem with heads, tails, release dates and deadlines that appears in the job-shop scheduling problem. [ABSTRACT FROM AUTHOR] more...

Jafari and Moslehi (J Glob Optim 54:389-404, ) state that certain single-machine scheduling problems with linear job deterioration are NP-hard. We show that this is not the case for the maximum lateness minimization problem and point out the issues in the analysis of Jafari and Moslehi (J Glob Optim 54:389-404, ). [ABSTRACT FROM AUTHOR] more...