Narrow Results

In the production scheduling of prefabricated components, we study an online $m$ parallel-batch machines scheduling model considering learning effect jobs with $f$ incompatible job families to minimize the makespan in this paper, where the capacity of batch is unbounded. Job families indicate that a job must belong to some job family and jobs of distinct job families are incapable to be executed in the same batch. The information of each job including its basic processing time $b_j$ and release time $r_j$ is unknown in advance and is revealed at the instant of its arrival. Moreover, the actual processing time of job $J_j$ with learning effect is $p_j=b_j(a-bt)$, where $a$ and $b$ are non-negative parameters and $t$ denotes the starting time of prefabricated job $J_j$, respectively. When $m=f$, we propose an online algorithm with a competitive ratio of $2-b{b}_{min}$. Furthermore, the performance of the online algorithm is demonstrated by numerical experiments.

This paper deals with the machine scheduling problems with the effects 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. We introduce polynomial solutions for some single machine problems and flow shop problems. The performance measures include makespan, total completion time, total weighted completion time, and maximum lateness.

This paper investigates the impact of learning curve effect on setup cost for the continuous review inventory model involving controllable lead time with the mixture of backorder and partial lost sales. A learning curve is a well known tool which describes the relation between the performance of a task and the number of repetitions of that task. The objective of this study is to minimize the expected total annual cost by simultaneously optimizing order quantity, safety factor and lead time under different setup learning rates. There are two models considered in the paper, one with normal demand distribution and another with general demand distribution having both mean and variance known and finite. Numerical examples are presented to illustrate the procedures of the proposed solution algorithms, along with the savings on the total costs of the models with the inclusion of the learning effect on setup.

Consider a batch-sizing problem, where all jobs are identical or similar, and a unit processing time (p = 1) is specified for each job. To minimize the total completion time of jobs, partitioning jobs into batches may be necessary. Learning effect from setup repetition makes small-sized batches; on the contrary, job's learning effect results in large-sized batches. With their collaborative influence, we develop a forward dynamic programming (DP) algorithm to determine the optimal number of batches and their optimal integer sizes. The computation effort required by this DP algorithm is a polynomial function of job size.

In the paper, single machine scheduling problems with a learning effect and a rate-modifying activity are considered. Under the learning effect, the processing time of a job is a decreasing function of its position in the sequence. The rate-modifying activity is an event that can change the speed of the machine, and hence the processing time of jobs after the activity. The following objective functions are considered: the makespan, the total earliness, tardiness and completion time penalty, and the total earliness, tardiness, due-window starting time and due-window size penalty. Polynomial time algorithms are proposed to optimally solve the problems.

We model the impact of information visibility in a two-level supply chain consisting of independent retailers who share upstream supply. The manufacturer supplies similar products to the two retailers and each retailer serves its independent end market. Retailers face one period of demand and satisfy the demand by ordering in the first period or back-ordering some of the demand and satisfying it in the second period. The wholesale price in the second period is decreasing in the total order size across the two retailers in the first period. This decrease in wholesale price captures the market learning effect of aggregate orders that has been extensively documented in empirical literature. We use a game-theoretic framework to investigate the ex-ante incentives for retailers to share their private demand information. We show that: (1) retailers have no incentives to share information about their private values when equilibrium order quantities are interior, i.e., the order size is between zero and the demand; (2) partial information sharing may be the equilibrium strategy for retailers when equilibrium order quantities are binding on the demand. Finally, numerical examples are provided for illustration. This paper thus identifies conditions under which different levels of information sharing may be the equilibrium outcomes in a supply chain.

A single-machine two-agent scheduling problem with a truncation learning effect is being addressed in the study. The truncation learning effect means that the actual processing time of a job is a function of the sum of processing times of already scheduled jobs and a control parameter. The aim is to find an optimal schedule to minimize the total weighted completion time of jobs of the first agent under the circumstances that no tardy job is allowed for the second agent. A branch-and-bound and three heuristic-based genetic algorithms (GAs) are proposed to solve the problem. Also presented in the study are the computational results of all proposed algorithms.

We consider single-machine scheduling problem in which the processing time of a job is a function of its position in a sequence, 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. The problem is modeled as an assignment problem, and thus can be solved in polynomial time. Some extensions of the problem are also shown.

Two results in a recent paper by Wang and Cheng [Wang, J-B and TCE Cheng (2007). Asia-Pacific Journal of Operational Research, 24, 245–261] are incorrect because job processing times are variable due to both deteriorating jobs and learning effects, which is not taken into account by the authors. In this note, we show by a counter-example that the published results are incorrect.

We consider a single-machine common due-window assignment scheduling problem, in which the processing time of a job is a function of its position in a sequence and its resource allocation. The window location and size, along with the associated job schedule that minimizes a certain cost function, are to be determined. This function is made up of costs associated with the window location, window size, earliness, and tardiness. For two different processing time functions, we provide a polynomial time algorithm to find the optimal job sequence and resource allocation, respectively.

The note deals with machine scheduling problems with a more general learning effect model, i.e., the actual job processing time is a function of the sum of the function of the processing times of the jobs already processed and job position. We show that some single machine scheduling problems are still polynomially solvable under the proposed model. We also show that some special cases of the flow shop scheduling problems can be solved in polynomial time.

Job learning and deterioration coexist in many realistic machine-job scheduling situations. However, in literature, the constructed forms of the machine scheduling models with job learning and/or deteriorating effects were specific types of functions, which constrained their applicability in practice. This paper introduces a new single-machine scheduling model, where the actual processing time of a job is a general function of its starting time as well as scheduled position, which shows a broad generalization in contrast to that of certain existing models. For three objectives corresponding to the single-machine scheduling problem–total weighted completion time, discounted total weighted completion time, and maximum lateness — this paper presents their respective approximation result on the basis of the worst-case bound analysis from the optimal algorithm. The results demonstrate that under our proposed model, minimization of scheduling operations such as the makespan, sum of the kth power of completion times, and total lateness are polynomially solvable. Moreover, under some feasible conditions for the scheduling parameters, the minimum optimization problems of the total weighted completion time, discounted total weighted completion time, maximum lateness, and total tardiness are all recognized as polynomial forms and their solutions are provided.

This paper considers single-machine scheduling with learning effect, deteriorating jobs and convex resource dependent processing times, i.e., the processing time of a job is a function of its starting time, its position in a sequence and its convex resource allocation. The objective is to find the optimal sequence of jobs and the optimal convex resource allocation separately to minimize a cost function containing makespan, total completion (waiting) time, total absolute differences in completion (waiting) times and total resource cost. It is proved that the problem can be solved in polynomial time.

This paper considers the single machine scheduling with learning effect, resource allocation and deteriorating maintenance activity simultaneously. For the convex resource allocation consumption function, we provide a bicriteria analysis where the first (schedule) criterion is to minimize the total weighted sum of makespan, total completion time and total absolute differences in completion times, and the second (resource) criterion is to minimize the total weighted resource consumption. Our aim is to find the optimal resource allocations and job sequence that minimize the three different models of considering the two criterion. We show that these three models are polynomially solvable respectively.

In this paper, the flow shop resource allocation scheduling with learning effect and position-dependent weights on two-machine no-wait setting is considered. Under common due date assignment and slack due date assignment rules, a bi-criteria analysis is provided. The optimality properties and polynomial time algorithms are developed to solve four versions of the problem. For a special case of the problem, it is proved that the problem can be optimally solved by a lower order algorithm.

This paper investigates a classic online scheduling problem with learning effect on a single machine. Specifically, a number of independent jobs that arrive online over time will be processed on a single machine and learning effect implies that the real processing time of job $J_j$ is a non-increasing function of its position $h$, i.e., $p_{jh}=p_j{\alpha }^{h-1}$, where $p_j$ is the basic processing time of job $J_j$ and $0<\alpha <1$ is the learning index. Our goal is to minimize the total completion time of all jobs. For the problem, we develop a deterministic polynomial time online algorithm called Delayed Shortest Basic Processing Time (DSBPT) and state that it is an online algorithm with a competitive ratio of 2, which matches the lower bound of the online scheduling problem we focus on.

In this paper, different due-window assignment flow shop scheduling problem with learning effect and resource allocation is considered. Under two machine no-wait flow shop setting, the goal is to determine the due-window starting time, due-window size, optimal resource allocation and the optimal sequence of all jobs. A bicriteria analysis of the problem is provided where the first criterion is to minimize the scheduling cost (including earliness-tardiness penalty, due-window starting time and due-window size of all jobs) and the second criterion is to minimize the resource consumption cost. It is shown that four versions about scheduling cost and resource consumption cost can be solved in polynomial time.

Scheduling problems with variable processing times and past-sequence-dependent delivery times are considered on a single-machine. The delivery times of jobs depend on their waiting times of processing. A job’s actual processing time depends on its position in a sequence, its starting time and its allocation of non-renewable resources. Under the linear resource consumption function, the goal (version) is to determine the optimal sequence and optimal resource allocation such that the sum of scheduling cost and total resource consumption cost is minimized. Under the convex resource consumption function, three versions of the scheduling cost and total resource consumption cost are discussed. We prove that these four versions can be solved in polynomial time, respectively. Some applications are also given by using the scheduling cost, which involve the makespan, total completion time, total absolute differences in completion times (TADC), and total absolute differences in waiting times (TADW).

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.

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.