Single-machine scheduling with time-and-resource-dependent processing times

We consider single-machine scheduling problems in which the processing time of a job is a function of its starting time and its resource allocation. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. We concentrate on two goals separately, namely, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. We show that the problems remain polynomially solvable under the proposed model.     

Single-machine scheduling with convex resource dependent processing times and deteriorating jobs

In this study, we consider scheduling problems with convex resource dependent processing times and deteriorating jobs, in which the processing time of a job is a function of its starting time and its convex resource allocation. The objective is to find the optimal sequence of jobs and the optimal convex resource allocation separately. This paper focus on the single-machine problems with objectives of minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost, and a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. It shows that the problems remain polynomially solvable under the proposed model.     

Parallel-machine scheduling with past-sequence-dependent delivery times and learning effect

This paper considers identical parallel-machine scheduling problem with past-sequence-dependent (psd) delivery times and learning effect. In electronic manufacturing industry, an electronic component may be exposed to certain electromagnetic field and requires an extra time for eliminating adverse effect after the main processing. The extra time is modeled as past-sequence-dependent delivery time in the literature, which is proportional to the waiting time in the system. It is also observed that the learning process reflects a decrease in the processing time as a function of the number of repetitions, i.e., as a function of the job position in the sequence. In practice, one often has to deal with the scheduling problems with psd delivery times and learning effect. Identical parallel-machine setting is considered because the occurrence of resources in parallel is common in the real world. In this paper, three objectives are the minimization of the total absolute deviation of job completion times, the total load on all machines and the total completion time. We develop polynomial algorithms to optimally solve these problems.     

Single-machine scheduling to minimize total absolute differences in waiting times with deteriorating jobs

In this paper we consider a single-machine scheduling problem with simple linear deterioration. By simple linear deterioration, we mean that the processing time of a job is a simple linear function of its execution starting time and its deterioration rate. The objective is to find a schedule that minimizes total absolute differences in waiting times. We show that the optimal schedule is V-shaped: jobs are arranged in descending order of their deterioration rates if they are placed before the job with the smallest deterioration rate, but in ascending order of their deterioration rates if placed after it. We prove other several properties of an optimal schedule, and introduce two efficient heuristic algorithms that are tested against a lower bound. We also provide computational results to evaluate the performance of the heuristic algorithms.     

Single-machine scheduling with both deterioration and learning effects

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.     

Unrelated parallel machines scheduling with deteriorating jobs and resource dependent processing times

We consider unrelated parallel machines scheduling problems involving resource dependent (controllable) processing times and deteriorating jobs simultaneously, i.e., the actual processing time of a job is a function of its starting time and its resource allocation. Two generally resource consumption functions, the linear and convex resource, were investigated. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. This paper focus on the objectives of minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost, and a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. If the number of unrelated parallel machines is a given constant, we show that the problems remain polynomially solvable under the proposed model.     

Single machine scheduling problems with controllable processing times and total absolute differences penalties

In this paper, we consider single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost. The problem is modelled as an assignment problem, and thus can be solved with the well-known algorithms. For the case where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution.     

带有退化效应和序列相关运输时间的排序问题

考虑带有退化效应和序列相关运输时间的单机排序问题. 工件的加工时间是其开工时间的简单线性增加函数. 当机器单个加工工件时, 极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的, EDD序对于极小化最大延迟问题不是最优排序, 另外, 就交货期和退化率一致情形给出了一最优算法. 当机器可分批加工工件时, 分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法.     

Parallel machines scheduling with deteriorating and learning effects

In this paper parallel identical machines scheduling problems with deteriorating jobs and learning effects are considered. In this model, job processing times are defined by functions of their starting times and positions in the sequence. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time and total absolute differences in completion times; minimizing a cost function containing total waiting time and total absolute differences in waiting times. We show that the problems remain polynomially solvable under the proposed model.     

A note on single-machine scheduling with decreasing time-dependent job processing times

In this note we consider some single-machine scheduling problems with decreasing time-dependent job processing times. Decreasing time-dependent job processing times means that its processing time is a non-increasing function of its execution start time. We present polynomial solutions for the sum of squared completion times minimization problem, and the sum of earliness penalties minimization problem subject to no tardy jobs, respectively. We also study two resource constrained scheduling problems under the same decreasing time-dependent job processing times model and present algorithms to find their optimal solutions.     

Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration

In this paper we introduce a new model of joint start-time dependent learning and position dependent aging effects into single-machine scheduling problems. The machine may need maintenance to improve its production efficiency. The objectives are to find jointly the optimal maintenance position and the optimal sequence such that the makespan, the total completion time, and the total absolute deviation of completion times (TADC) are minimized. We also aim to determine jointly the optimal maintenance position, the optimal due-window size and location, and the optimal sequence to minimize the sum of earliness, tardiness and due-window related costs function. We show that all the studied problems can be optimally solved by polynomial time algorithms.     

Single-machine scheduling with deteriorating functions for job processing times

In many realistic scheduling settings a job processed later consumes more time than when it is processed earlier – this phenomenon is known as scheduling with deteriorating jobs. In the literature on deteriorating job scheduling problems, majority of the research assumed that the actual job processing time of a job is a function of its starting time. In this paper we consider a new deterioration model where the actual job processing time of a job is a function of the processing times of the jobs already processed. We show that the single-machine scheduling problems to minimize the makespan and total completion time remain polynomially solvable under the proposed model. In addition, we prove that the problems to minimize the total weighted completion time, maximum lateness, and maximum tardiness are polynomially solvable under certain agreeable conditions.     

Some single-machine scheduling with sum-of-processing-time-based and job-position-based processing times

The single-machine scheduling problems with position and sum-of-processing-time based processing times are considered. The actual processing time of a job is defined by function of its scheduled position and total normal processing time of jobs in front of it in the sequence. We provide optimal solutions in polynomial time for some special cases of the makespan minimization and the total completion time minimization. We also show that an optimal schedule to be a V-shaped schedule in terms of the normal processing times of jobs for the total completion time minimization problem and the makespan minimization problem.     

Single-machine scheduling problems with past-sequence-dependent setup times

This paper studies single-machine scheduling problems with setup times which are proportionate to the length of the already scheduled jobs, that is, with past-sequence-dependent or p-s-d setup times. The following objective functions are considered: the maximum completion time (makespan), the total completion time, the total absolute differences in completion times and a bicriteria combination of the last two objective functions. It is shown that the standard single-machine scheduling problem with p-s-d setup times and any of the above objective functions can be solved in O(nlog n) time (where n is the number of jobs) by a sorting procedure. It is also shown that all of our results extend to a “learning” environment in which the p-s-d setup times are no longer linear functions of the already elapsed processing time due to learning effects.     

Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties

In this paper we consider parallel identical machines scheduling problems with deteriorating jobs. In this model, job processing times are defined by functions of their starting times. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remains polynomially solvable under the proposed model.     

Worst-case analysis for flow shop scheduling problems with an exponential learning effect

A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling problems with an exponential learning effect. By the exponential learning effect, we mean that the processing time of a job is defined by an exponent function of its position in a processing permutation. The objective is to minimize one of the four regular performance criteria, namely, the total completion time, the total weighted completion time, the discounted total weighted completion time, and the sum of the quadratic job completion times. We present heuristic algorithms by using the optimal permutations for the corresponding single-machine scheduling problems. We also analyse the worst-case bound of our heuristic algorithms.     

Note on “A note on single-machine group scheduling problems with position-based learning effect”

In a recent paper, Lee and Wu [W.-C. Lee, C.-C. Wu, A note on single-machine group scheduling problems with position-based learning effect, Appl. Math. Model. 33 (2009) 2159–2163] proposed a new group scheduling learning model where the learning effect not only depends on the job position, but also depends on the group position. They investigate the makespan and the total completion time minimization problems on a single-machine. As for the total completion time minimization problem, they assumed that the numbers of jobs in each group are the same and the group normal setup and the job normal processing times are agreeable. Under the assumption conditions, they showed that the total completion time minimization problem can be optimally solved in polynomial time solution. However, the assumption conditions for the total completion time minimization problem do not reflect actual practice in many manufacturing processes. Hence, in this note, we propose other agreeable conditions and show that the total completion time minimization problem remains polynomially solvable under the agreeable conditions.     

Single machine scheduling problems with general position-dependent processing times and past-sequence-dependent delivery times

This paper considers single machine scheduling with past-sequence-dependent (psd) delivery times, in which the processing time of a job depends on its position in a sequence. We provide a unified model for solving single machine scheduling problems with psd delivery times. We first show how this unified model can be useful in solving scheduling problems with due date assignment considerations. We analyze the problem with four different due date assignment methods, the objective function includes costs for earliness, tardiness and due date assignment. We then consider scheduling problems which do not involve due date assignment decisions. The objective function is to minimize makespan, total completion time and total absolute variation in completion times. We show that each of the problems can be reduced to a special case of our unified model and solved in O(n ³) time. In addition, we also show that each of the problems can be solved in O(nlogn) time for the spacial case with job-independent positional function.     

Single machine group scheduling with time and position dependent processing times

In the paper two resource constrained single-machine group scheduling problems with time and position dependent processing times are considered. By time and position dependent processing times and group technology assumption, we mean that the processing time of a job is defined by the function of its starting time and position in the group, and the group setup times of a group is a positive strictly decreasing continuous function of the amount of consumed resource. We present polynomial solutions for the makespan minimization problem under the constraint that the total resource consumption does not exceed a given limit, and the total resource consumption minimization problem under the constraint that the makespan does not exceed a given limit, respectively.     

Scheduling jobs with position-dependent processing times

The paper is devoted to some single machine scheduling problems, where job processing times are defined by functions dependent on their positions in the sequence. It is assumed that each job is available for processing at its ready time. We prove some properties of the special cases of the problems for the following optimization criteria: makespan, total completion time and total weighted completion time. We prove strong NP-hardness of the makespan minimization problem for two different models of job processing time. The reductions are done from the well-known 3-Partition Problem. In order to solve the makespan minimization problems, we suggest the Earliest Ready Date algorithms, for which the worst-case ratios are calculated. We also prove that the makespan minimization problem with job ready times is equivalent to the maximum lateness minimization problem.