An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem

Recently, Shabtay and Bensoussan (2012) developed an original exact pseudo-polynomial algorithm and an efficient $\upvarepsilon $ -approximation algorithm (FPTAS) for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem. The complexity of the FPTAS is $O$ (( $n^{4}/\upvarepsilon $ )log( $n$ / $\upvarepsilon $ )), where $n$ is the number of jobs. In this note we suggest another pseudo-polynomial algorithm that can be converted to a new FPTAS which improves Shabtay–Bensoussan’s complexity result and runs in $O(n^{3}/\upvarepsilon )$ time.     

A note: Maximizing the weighted number of just-in-time jobs on a proportionate flowshop

In most cases, an extension of a polynomial time solution of a scheduling problem on a single machine to a proportionate flowshop leads to a similar (polynomial time) solution. One of the rare cases where the problem becomes hard, is that of maximizing the weighted number of Just-in-Time jobs on a proportionate flowshop. We introduce a (pseudo-polynomial) solution algorithm for this problem, which is faster by a factor of n than the algorithm published in the literature. We also introduce a (polynomial time) solution algorithm for the “no-wait” proportionate flowshop.     

Scheduling unrelated parallel machines with optional machines and jobs selection

In this paper we study two generalizations of the well known unrelated parallel machines scheduling problem under makespan (C_max) minimization. First, a situation in which not every available parallel machine should be used and it is desirable to employ only a subset of the parallel machines. This is referred to as “Not All Machines” or NAM in short. This environment applies frequently in production shops where capacity exceeds demand or when production capacity can be lent to third companies. Also, NAM can be used to increase production capacity and it is not clear how many additional machines should be acquired. The second studied generalization has been referred to as “Not All Jobs” or NAJ. Here, there is no obligation to process all available jobs. We propose Mixed Integer Programming mathematical formulations for both NAM and NAJ, and it is shown that the latter can be effectively solved with modern commercial solvers. We also present three algorithms to solve the NAM problem. These algorithms are compared with the proposed MIP formulation when solved with IBM ILOG CPLEX 12.1. Comprehensive computational and statistical experiments prove that our proposed algorithms significantly improve the results given by the solver.     

Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs

We consider the scheduling problem in which two agents (agents A and B), each having its own job set (containing the A-jobs and B-jobs, respectively), compete to process their own jobs in a two-machine flowshop. Each agent wants to maximize a certain criterion depending on the completion times of its jobs only. Specifically, agent A desires to maximize either the weighted number of just-in-time (JIT) A-jobs that are completed exactly on their due dates or the maximum weight of the JIT A-jobs, while agent B wishes to maximize the weighted number of JIT B-jobs. Evidently four optimization problems can be formulated by treating the two agents’ criteria as objectives and constraints of the corresponding optimization problems. We focus on the problem of finding the Pareto-optimal schedules and present a bicriterion analysis of the problem. Solving this problem also solves the other three problems of bicriterion scheduling as a by-product. We show that the problems under consideration are either polynomially or pseudo-polynomially solvable. In addition, for each pseudo-polynomial-time solution algorithm, we show how to convert it into a two-dimensional fully polynomial-time approximation scheme for determining an approximate Pareto-optimal schedule. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms.     

Maximizing the weighted number of just-in-time jobs in flow shop scheduling

In this paper we consider the maximization of the weighted number of just-in-time jobs that should be completed exactly on their due dates in n-job, m-machine flow shop problems. We show that a two-machine flow shop problem is NP-complete. When job weights are all identical, we show that the problem can be solved in polynomial time. We also show that a three-machine flow shop problem with identical job weights is NP-hard in the strong sense by reduction of the 3-partition problem.     

A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival

This paper addresses a scheduling problem motivated by scheduling of diffusion operations in the wafer fabrication facility. In the target problem, jobs arrive at the batch machines at different time instants, and only jobs belonging to the same family can be processed together. Parallel batch machine scheduling typically consists of three types of decisions—batch forming, machine assignment, and batch sequencing. We propose a memetic algorithm with a new genome encoding scheme to search for the optimal or near-optimal batch formation and batch sequence simultaneously. Machine assignment is resolved in the proposed decoding scheme. Crossover and mutation operators suitable for the proposed encoding scheme are also devised. Through the experiment with 4860 problem instances of various characteristics including the number of machines, the number of jobs, and so on, the proposed algorithm demonstrates its advantages over a recently proposed benchmark algorithm in terms of both solution quality and computational efficiency.     

A variable neighborhood search approach for planning and scheduling of jobs on unrelated parallel machines

In this paper, we study a planning and scheduling problem for unrelated parallel machines. There are n jobs that have to be assigned and sequenced on m unrelated parallel machines. Each job has a weight that represents the priority of the corresponding customer order, a given due date, and a release date. An Automated Guided Vehicle is used to transport at maximum Load _max jobs into a storage space in front of the machines in a given period of time. We consider t _max consecutive periods. We are interested in minimizing the total weighted tardiness of the jobs across the periods. This measure is important when we are interested in a good on-time delivery performance. We present an appropriate mixed integer program. To solve this NP-hard problem, we develop a heuristic methodology based on decomposition and variable neighborhood search (VNS). The proposed approaches are assessed using randomly generated problem instances. We compare them with a simple heuristic based on decomposition and list scheduling using the Apparent Tardiness Cost dispatching rule. The results demonstrate that the heuristic approach based on VNS performs comparably to the mixed integer program while having reasonable solution times and outperforms the simple heuristic and a genetic algorithm (GA) from previous research.     

Maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times

We study the problem of maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times. Unlike the vast majority of the literature, we do not restrict ourselves to a specific model of processing time function. Rather, we assume that the processing time function can be of any functional structure that is according to one of the following two cases. The first is the case where the job processing times are under a learning effect, i.e., each job processing time is a non-increasing function of its position in the sequence. In the second case, an aging effect is assumed, i.e., each job processing time is a non-decreasing function of its position in the sequence. We prove that the problem is strongly $\mathcal{N }\mathcal{P }$ N P -hard under a learning effect, even if all the weights are identical. When there is an aging effect, we introduce a dynamic programming (DP) procedure that solves the problem with arbitrary weights in $O(n^{3})$ O ( n 3 ) time (where $n$ n is the number of jobs). For identical weights, a faster optimization algorithm that runs in $O(n\log n)$ O ( n log n ) time is presented. We also extend the analysis to the case of scheduling on a set of $m$ m parallel unrelated machines and provide a DP procedure that solves the problem in polynomial time, given that $m$ m is fixed and that the jobs are under an aging effect.     

A neural network algorithm for servicing jobs with sequential and parallel machines

We consider the FJ‖C _max problem of optimal servicing with respect to performance for a given set of jobs by sequential and parallel machines. The problem FJ‖C _max is a generalization of the classical J‖C _max problem for the case when the servicing system has not only sequential but also parallel (identical) machines. We propose a two-stage algorithm for a heuristic solution of problem FJ‖C _max On the first stage, we solve the problem J‖C _max, i.e., we assume that the servicing system does not have parallel machines. On the second stage, operations are distributed over parallel machines. On both stages of the algorithm, we use neural network decision making models. The efficiency of a neural network algorithm for the problem J‖C _max and problem FJ‖C _max was evaluated on 20 test examples obtained from 20 known J‖C _max problems by including into the servicing system a random number of copies of sequential machines.     

Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines

We consider the problem of scheduling a maximum profit selection of equal length jobs on m   identical machines. Jobs arrive online over time and the goal is to determine a non-preemptive schedule which maximizes the total profit of the scheduled jobs. Let the common processing requirement of the jobs be p>0$p>0$. For each job j_i, i=1,…,n we are given a release time r_i (at which the job becomes known) and a deadline _ri+p+_δi$r_i+p+{\delta }_i$. If the job is scheduled and completed before the deadline, a profit of w_i is earned.     

A search heuristic for just-in-time scheduling in parallel machines

In recent years the Just-in-Time (JIT) production philosophy as been adopted by many companies around the world. This has motivated the study of scheduling models that embrace the essential components of JIT systems. In this paper, we present a search heurustic for the weighted earliness penalty problem with deadlines in parallel identical machines. Our approach combines elements of the solution methods known as greedy randomized adaptive search procedure (GRASP) and tabu search. It also uses a branch-and-bound post-processor to optimize individually the sequence of the jobs assigned to each machine.     

Sequencing unreliable jobs on parallel machines

This paper addresses an allocation and sequencing problem motivated by an application in unsupervised automated manufacturing. There are n independent jobs to be processed by one of m machines or units during a finite unsupervised duration or shift. Each job is characterized by a certain success probability p _i , and a reward r _i which is obtained if the job is successfully carried out. When a job fails during processing, the processing unit is blocked, and the jobs subsequently scheduled on that machine are blocked until the end of the unsupervised period. The problem is to assign and sequence the jobs on the machines so that the expected total reward is maximized. This paper presents the following results for this problem and some extensions: (i) a polyhedral characterization for the single machine case, (ii) the proof that the problem is NP-hard even with 2 machines, (iii) approximation results for a round-robin heuristic, (iv) an effective upper bound. Extensive computational results show the effectiveness of the heuristic and the bound on a large sample of instances.     

An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem

In this work, we tackle the problem of scheduling a set of jobs on a set of unrelated parallel machines with minimising the total weighted completion times as performance criteria. The iterated greedy metaheuristic generates a sequence of solutions by iterating over a constructive heuristic using destruction and construction phases. In the last few years, iterated greedy has been employed to solve a considerable number of problems. This is because it is based on a very simple principle, it is easy to implement, and it often exhibits an excellent performance. Moreover, scalability for high-dimensional problems becomes an essential requirement for modern optimisation algorithms. This paper proposes an iterated greedy model for the above-mentioned scheduling problem to tackle large-size instances. The benefits of our proposal in comparison to existing metaheuristics proposed in the literature are experimentally shown.     

带不相关并行机的阻塞FFP的混合遗传算法

针对带释放时间和运输时间的柔性流水车间问题,每个处理阶段含不相关并行机,且中间无缓冲,以最小化所有工件的加权完成时间之和为目标,提出一种基于遗传算法的EGA&LS优化方法.采用二维矩阵编码方式产生初始种群,执行交叉和变异操作后提出基于工件的多点交换、基于机器号的单点交换和基于工件的多点变异3种邻域结构来产生邻域解.为验...     

Online scheduling of equal-length jobs with incompatible families on multiple batch machines to maximize the weighted number of early jobs

This paper studies the online scheduling of equal-length jobs with incompatible families on multiple batch machines which can process the jobs from a common family in batches, where each batch has a capacity b with $b=\infty$ in the unbounded batching and $b<\infty$ in the bounded batching. Each job J has an equal-length integral processing time $p>0$, an integral release time $r(J)?0$, an integral deadline $d(J)?0$ and a real weight $w(J)?0$. The goal is to determine a preemptive schedule with restart which maximizes the weighted number of early jobs. When $p=1$, we show that a simple greedy online algorithm has a competitive ratio 2, and establish the lower bound $2?1/b$. This means that the greedy algorithm is of the best possible for $b=\infty$. When p is any positive integer, we provide an online algorithm of competitive ratio $3+2\sqrt{2}$ for both $b=\infty$ and $b<\infty$. This is the first online algorithm for the problem with a constant competitive ratio.     

A hybrid GA-SA algorithm for just-in-time scheduling of multi-level assemblies

The environment is a manufacturing facility that produces multi-level assemblies in a Just-In-Time (JIT) fashion. The due-dates and lot-sizes of the end-items are given, and the objective is to determine a lot-for-lot operations schedule that minimizes the cumulative production lead-time. The scheduling problem within such an environment is NP-hard, and therefore, the performance of heuristics may vary depending on the specific problem instance. To address this problem an effective hybrid Genetic Algorithm-Simulated Annealing (GA-SA) algorithm is developed. The GA starts with an initial population generated by well known scheduling heuristics, a critical path heuristic, and randomly generated schedules. The scheduling work is shared by the GA and SA in two phases that alternate until convergence: (1) Phase I is the GA that crosses over solutions for different work-centers, and (2) Phase II is the SA that improves the sequence of operations on individual work-centers. The effectiveness of the proposed heuristic is assessed via numerical studies.     

A multi objective volleyball premier league algorithm for green scheduling identical parallel machines with splitting jobs

Parallel machine scheduling is one of the most common studied problems in recent years, however, this classic optimization problem has to achieve two conflicting objectives, i.e. minimizing the total tardiness and minimizing the total wastes, if the scheduling is done in the context of plastic injection industry where jobs are splitting and molds are important constraints. This paper proposes a mathematical model for scheduling parallel machines with splitting jobs and resource constraints. Two minimization objectives - the total tardiness and the number of waste - are considered, simultaneously. The obtained model is a bi-objective integer linear programming model that is shown to be of NP-hard class optimization problems. In this paper, a novel Multi-Objective Volleyball Premier League (MOVPL) algorithm is presented for solving the aforementioned problem. This algorithm uses the crowding distance concept used in NSGA-II as an extension of the Volleyball Premier League (VPL) that we recently introduced. Furthermore, the results are compared with six multi-objective metaheuristic algorithms of MOPSO, NSGA-II, MOGWO, MOALO, MOEA/D, and SPEA2. Using five standard metrics and ten test problems, the performance of the Pareto-based algorithms was investigated. The results demonstrate that in general, the proposed algorithm has supremacy than the other four algorithms.

     

A memetic algorithm to solve an unrelated parallel machine scheduling problem with auxiliary resources in semiconductor manufacturing

In this paper, we propose a metaheuristic for solving an original scheduling problem with auxiliary resources in a photolithography workshop of a semiconductor plant. The photolithography workshop is often a bottleneck, and improving scheduling decisions in this workshop can help to improve indicators of the whole plant. Two optimization criteria are separately considered: the weighted flow time (to minimize) and the number of products that are processed (to maximize). After stating the problem and giving some properties on the solution space, we show how these properties help us to efficiently solve the problem with the proposed memetic algorithm, which has been implemented and tested on large generated instances. Numerical experiments show that good solutions are obtained within a reasonable computational time.