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 study aims to deal with a dynamic scheduling problem of a real Flow Shop follow-up of an assembly process considering the specific constraints and requirements of a brass accessories manufacturing (BAM) company. We basically set up a Digital Twin-driven dynamic scheduling approach for Industry 4.0 by addressing uncertainties of machine availability. In fact, the setup of this Digital Twin (DT) is the outcome of the combination of both optimization and simulation. For the first step, we have elaborated a Mixed Integer Linear Programming (MILP) scheduling model by taking into account the dedicated requisites of our case study. Concerning simulation, a 3D simulation platform of a workshop producing brass accessories controlled by a Cyber-Physical Production System (CPPS) has been developed, in our previous work, including constraints and stochastic aspects. The simulation constraints are difficult or impossible to be modeled in the MILP model. These designs are integrated with the real workshop to construct the Digital Twin. The proposed tool enables the rescheduling of production orders based on machine disturbances and unpredictability. Validation scenarios have been designed and conducted to highlight the efficacy of the Digital Twin approach utilizing the brass accessories case study. We are confident that this represents the initial endeavor addressing the optimization of production rescheduling in a flow shop follow-up of a mixed assembly system.

We consider two-machine flow shop problems with exact delays. In this model, there are two machines, the upstream machine and the downstream machine. Each job j has two operations: the first operation has to be processed on the upstream machine and the second operation has to be processed on the downstream machine, subject to the constraint that the time interval between the completion time of the first operation and the start time of the second operation is exactly . We concentrate on the objectives of makespan and total completion time. For the makespan objective, we first show that the problem is strongly NP-hard even if there are only two possible delay values. We then show that some special cases of the problem are solvable in polynomial time. Finally, we design efficient approximation algorithms for the general case and some special cases. For the total completion time objective, we give optimal polynomial-time algorithm for a special case and an efficient approximation algorithm for another one.

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.

This paper discusses about the flow shop scheduling problems using shortest processing time, earliest due date (EDD), Nawaz, Enscore, and Ham (NEH), NEH-EDD, and modified-NEH methods. The objective of this research is to determine the performance of these methods in minimizing makespan and total tardiness. Processing times and due dates were randomly generated, and computational studies were performed in Microsoft Visual Basic 6.0. The experiments are performed for small and medium data sets. Efficiency index, relative error, and run time measure the performance of each method. Experimental results showed that NEH has the best performance in minimizing the makespan in both data sets; these are 53.35 time unit for small data sets and 83.803 time unit for medium data sets. NEH-EDD has the best performance in minimizing total tardiness with 9.37 time unit for small data sets and 231.02 time unit for medium data sets. Modified-NEH, as the proposed method for minimizing makespan and total tardiness at the same time, has good enough result. For minimizing the makespan, modified-NEH results in 57.15 time unit for small data sets and 88.107 time unit for medium data sets. For minimizing total tardiness, the modified-NEH results in 14.21 time unit for small data sets and 246.57 time unit for medium sets.

This paper, proposes a hybrid fuzzy logic-based particle swarm optimization (PSO) with cross-mutated operation method for the minimization of makespan in permutation flow shop scheduling problem. This problem is a typical non-deterministic polynomial-time (NP) hard combinatorial optimization problem. In the proposed hybrid PSO, fuzzy inference system is applied to determine the inertia weight of PSO and the control parameter of the proposed cross-mutated operation by using human knowledge. By introducing the fuzzy system, the inertia weight becomes adaptive. The cross-mutated operation effectively forces the solution to escape the local optimum. To make PSO suitable for solving flow shop scheduling problem, a sequence-order system based on the roulette wheel mechanism is proposed to convert the continuous position values of particles to job permutations. Meanwhile, a new local search technique namely swap-based local search for scheduling problem is designed and incorporated into the hybrid PSO. Finally, a suite of flow shop benchmark functions are employed to evaluate the performance of the proposed PSO for flow shop scheduling problems. Experimental results show empirically that the proposed method outperforms the existing hybrid PSO methods significantly.

This paper deals with semi-online scheduling on m-batch-machine flow shop. The objective is to minimize the makespan. A parallel batch processing machine can handle up to B jobs simultaneously. We study an unbounded model where B = ∞. The jobs that are processed together construct a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. The problem is online in the sense that jobs arrive over time. Let p_{i, j}(i = 1,…,m) denote the processing time of job J_j on machines M_i, respectively. Let J_j+1 be the following job of J_j in a job instance. We study semi-online problem with jobs' nondecreasing processing times. We focus on the case where p_{1, j} = ⋯ = p_{m, j} for i = 1, …, m and p_{i, j+1} ≥ βp_{i, j} (β ≥ 1). For this problem, we propose an optimal algorithm with a competitive ratio .