Deteriorating jobs and learning effects on a single-machine scheduling with past-sequence-dependent setup times

In this paper, we consider the single-machine setup times scheduling with the effects of learning and deterioration. By the effects of learning and deterioration, we mean that the actual processing time of a job depends not only on the processing times of the jobs already processed but also on its scheduled position. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We show that the problems to minimize the makespan, the total completion time, and the sum of the $\mathit{\delta}$ th ( ${\mathit{\delta}} \geq 0$ ) power of job completion times are polynomially solvable. We also show that the total weighted completion time minimization problem, the maximum lateness minimization problem, and the number of tardy jobs minimization problem can be solved in polynomial time under certain conditions.     

On the scheduling with past-sequence-dependent setup times and learning effects on a single machine

This paper deals with a single-machine scheduling problem with setup time and learning effects. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are job-independent and past-sequence-dependent, and the learning effects are job-independent and position-dependent. The objective is to minimize the sum of earliness penalties subject to no tardy jobs. Wang, Wang, Gao, and Huang [Int J Adv Manuf Technol 48: 739–746, 2010] showed that an optimal sequence for this problem could be obtained by arranging jobs in non-increasing order of processing times. In this paper, we first demonstrate that this result is incorrect, and then introduce new exact solution strategies that polynomially solve problems whose earliness penalties are strictly increasing functions of job earliness. Polynomial time solutions are also presented for some special cases.     

Some single-machine scheduling problems with past-sequence-dependent setup times and a general learning effect

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.     

Note to: Deteriorating jobs and learning effects on a single-machine scheduling with past-sequence-dependent setup times

Some results in a recent paper (Yin et al., Int J Adv Manuf Technol 46:707–714, 2010) are incorrect. In this note, we show by a counterexample that the results are incorrect.     

A note on deteriorating jobs and learning effects on a single-machine scheduling with past-sequence-dependent setup times

A result in a recent paper by Yin et al. (Int J Adv Manuf Technol 46:707–714, (2010) is incorrect because job processing times are variable due to both deteriorating jobs and learning effects, a consideration which was not taken into account by the authors. In this note, we show by a counter-example that the published result is incorrect.     

Scheduling with past-sequence-dependent setup times and learning effects on a single machine

In this paper, we study the single-machine scheduling problems with learning effect and setup time considerations. The setup times are proportional to the length of the already-processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). The objective functions are to minimize the sum of the quadratic job completion times, the total waiting time, the total weighted completion time, the maximum lateness, the total absolute differences in waiting times, and the sum of earliness penalties subject to no tardy jobs, respectively. We show that the sum of the quadratic job completion times minimization problem, the total waiting time minimization problem, the total absolute differences in waiting times minimization problem, and the sum of earliness penalties minimization problem subject to no tardy jobs can be solved in polynomial time, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under some special cases.     

Single-machine group scheduling with linearly decreasing time-dependent setup times and job processing times

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.     

Single-machine scheduling with controllable processing times and learning effect

In this paper, we consider single-machine scheduling problem with controllable processing times and learning effect, i.e., processing times of jobs are controllable variables with linear costs and also are defined as functions of positions in a schedule. We concentrate on two goals separately, namely minimizing a cost function containing makespan, total completion time, total absolute differences in completion times, and total compression cost and minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times, and total compression cost. The problem is modeled as an assignment problem and thus can be solved with the well-known algorithms.     

Scheduling with deteriorating jobs and past-sequence-dependent setup times

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.     

Single-machine scheduling with a time-dependent deterioration

The paper deals with the single-machine scheduling problems with a time-dependent deterioration. By time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. We show that, even with the introduction of time-dependent deterioration to job processing times, the single-machine makespan minimization problem remains polynomially solvable. We also show that an optimal schedule of the total completion time minimization problem is V-shaped with respect to normal job processing times.     

Single-machine scheduling with a position-based learning effect and fuzzy processing times

In scheduling problems with learning effects, most researches assume that processing times are deterministic. This paper considers a single-machine scheduling problem with a position-based learning effect and fuzzy processing times, simultaneously. 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. A polynomial time algorithm is proposed for the problem where the objective is to minimize the total completion time. The solution procedure is based on applying the shortest processing time rule to triangular fuzzy processing times. Computational results show that our model gives better results than the model ignoring the uncertainty.     

Single-machine scheduling with simple linear deterioration to minimize earliness penalties

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.     

A deadlock-free scheduling with sequence-dependent setup times

This paper presents a novel approach to job shop scheduling with sequence-dependent setup times. The scheduling modeling is based on timed Petri nets. Control arcs are introduced to alleviate deadlocks, thus ensuring sequence-dependent setups. Based on siphon-related truncation, an efficient branch and bound algorithm for deadlock-free scheduling is devised. In addition, an effective priority rule is defined to handle large-scale problems. A series of experiments illustrate the validity of the priority rule and the scalability of our method for large-scale problems.     

Two single-machine scheduling problems with the effects of deterioration and learning

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.     

Single-machine scheduling with precedence constraints and decreasing start-time dependent processing times

In this paper we consider single-machine scheduling problems with decreasing start-time-dependent processing times, i.e., jobs whose processing times are a decreasing function of their starting times. In addition, the jobs are related by parallel chains and a series-parallel graph precedence constraint, respectively. It is shown that, for the problems of minimization of the total weighted completion time, polynomial algorithms exist.     

双目标函数下需要安装时间的平行多功能机排序问题

讨论了双目标函数下需要安装时间的平行多功能机排序问题。在该问题中,每个工件对应机器集合的一个子集,且每个工件只能在相应子集中的任一台机器上加工,工件分组,不同组中的工件连续加工需要安装时间,目标函数为极小化最大完工时间和安装次数。根据实际应用背景确定双目标排序问题的形式,并证明了该问题是NP—难的。设计了一个求启发式有效解的算法,首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后逐步改进最大完工时间和拆分工件组,从而得到一系列的启发式有效解。实验表明,该算法是实用而有效的。     

A note on single-machine scheduling problems with the effects of deterioration and learning

This paper studies 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 proposes two heuristics according to the corresponding single machine 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.     

Group scheduling with independent setup times, ready times, and deteriorating job processing times

Self-piercing riveting (SPR) is a high-speed mechanical fastening technique which is suitable for point-joining advanced lightweight sheet materials that are dissimilar, coated, and hard to weld. Major advances have been made in recent years in SPR technique. Latest literature relating to finite element analysis (FEA) of SPR joints is reviewed in this paper. The recent development in FEA of SPR joints are described with particular reference to three major factors that influence the success of SPR technique: SPR process, failure mechanism, and mechanical behavior of SPR joints. The main FE methods used in FEA of SPR joints are discussed and illustrated with brief case studies from the literature. Areas where further useful progress can be made are also identified.     

Single-machine scheduling with a sum-of-processing-time based learning effect and deteriorating jobs

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.     

Bicriteria scheduling of a two-machine flowshop with sequence-dependent setup times

A two-machine flowshop scheduling problem is addressed to minimize setups and makespan where each job is characterized by a pair of attributes that entail setups on each machine. The setup times are sequence-dependent on both machines. It is shown that these objectives conflict, so the Pareto optimization approach is considered. The scheduling problems considering either of these objectives are $ \mathcal{N}{\wp } - {\text{hard}} $ , so exact optimization techniques are impractical for large-sized problems. We propose two multi-objective metaheurisctics based on genetic algorithms (MOGA) and simulated annealing (MOSA) to find approximations of Pareto-optimal sets. The performances of these approaches are compared with lower bounds for small problems. In larger problems, performance of the proposed algorithms are compared with each other. Experimentations revealed that both algorithms perform very similar on small problems. Moreover, it was observed that MOGA outperforms MOSA in terms of the quality of solutions on larger problems.