Narrow Results

In this paper, we deal with the different due windows assignment proportionate flow shop problem with position-dependent weights, where the sequence is a permutation. The objective is to determine an optimal job sequence and due windows of all jobs such that the weighted sum of earliness–tardiness, the starting time and size of all due windows is to be minimized, where the weight is not related to the job but to the position in which some job is scheduled, i.e., position-dependent weights. According to a series of optimal properties, we prove that the problem can be solved in polynomial time $O(n^2)$, where $n$ is the number of jobs.

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.

Reinforcement learning (RL) is a state or action value based machine learning method which solves large-scale multi-stage decision problems such as Markov Decision Process (MDP) and Semi-Markov Decision Process (SMDP) problems. We minimize the makespan of flow shop scheduling problems with an RL algorithm. We convert flow shop scheduling problems into SMDPs by constructing elaborate state features, actions and the reward function. Minimizing the accumulated reward is equivalent to minimizing the schedule objective function. We apply on-line TD(λ) algorithm with linear gradient-descent function approximation to solve the SMDPs. To examine the performance of the proposed RL algorithm, computational experiments are conducted on benchmarking problems in comparison with other scheduling methods. The experimental results support the efficiency of the proposed algorithm and illustrate that the RL approach is a promising computational approach for flow shop scheduling problems worthy of further investigation.

In this study, we consider a permutation flow shop scheduling problem on a three-machine with deteriorating jobs (a deteriorating job means that the job's processing time is an increasing function of its starting time) so as to minimize the makespan. We model job deterioration as a function that is proportional to a linear function of time. For some special cases, we prove that the problem can be solved in polynomial time. We develop branch-and-bound and heuristic procedures for the general case. Computational experiments for the branch-and-bound algorithm and heuristic algorithm are presented.

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.

The $n$-job and $m$-machine permutation flow shop scheduling problem with a proportional deterioration is considered in which all machines process the jobs in the same order, i.e., a permutation schedule. A proportional deterioration means that the job deterioration as an increasing function that is proportional to a linear function of time. The objective is to minimize the makespan, i.e., the maximum completion time. When some dominant relationships between $m-1$ machines can be satisfied, we show that some special cases of the problem can be polynomial solvable. For the general case, we also propose a heuristic algorithm and give the computational experiments.

We consider a two-agent scheduling problem in a two-machine flow shop environment where each agent is responsible for his own set of jobs and wishes to minimize the makespan. The objective is to minimize one agent’s makespan, subject to the other’s objective of not exceeding a given threshold. It is known that the problem is NP-hard. Thus, we consider special cases such that the processing times of each agent have a special structure, and analyze their computational complexity.

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.

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.

The phenomenon of deterioration effects can reduce production efficiency caused by extended start time or other factors. Based on it, this paper considers the scheduling situations of the common due date assignment in a no-idle flow shop scheduling environment. Under the given four dominating relationships (i.e., increasing, decreasing, increasing-decreasing and decreasing-increasing dominating machines, correspondingly expressed as idm, ddm, idm–ddm and ddm–idm) between machines, the objective functions are, respectively, to minimize (1) the weighted sum of common due date and total earliness; and (2) the weighted sum of common due date, total earliness and total penalty factors of tardy jobs. It is verified that these problems can be solved in polynomial time under four dominating relationships.