Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs

We study the problem of nonpreemptively scheduling n jobs on m identical machines in parallel to maximize the weighted number of jobs that are completed exactly at their due dates. We show that this problem is solvable in polynomial time even if positive set-up times are allowed. Moreover, we show that if due date tolerances are permitted, then already the single-machine case is NP-hard even if all set-up times are zero and all weights are the same.Scope and purposeMost of the literature in the field of deterministic scheduling deals with regular measures of performance, that is with minimizing objective functions that are nondecreasing in job completion times. With the growing interest in just-in-time production, the demand for research into problems with irregular performance measures has considerably increased (see Baker and Scudder, Oper Res 38(1) (1990) 22). This note provides an efficient algorithm for finding nonpreemptive schedules that are optimal with respect to a special type of irregular performance measures in the case of identical machines in parallel.     

A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines

In this paper, we study a scheduling problem on identical parallel machines, in which a processing time and a due date are given for each job, and the objective is to maximize the number of just-in-time jobs. A job is called just-in-time if it is completed exactly on its due date. We discuss the known results, show that a recently published greedy algorithm for this problem is incorrect, and present a new quadratic time algorithm which solves the problem.     

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.     

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.     

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.     

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 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.     

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.     

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.     

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.     

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.     

求解不相关并行机混合流水线调度问题的人工蜂群算法

针对不相关并行机混合流水线调度问题的特点,设计了一种基于排列的编码和解码方法,提出了一种有效的人工蜂群算法.在引领蜂和跟随蜂搜索阶段采用3种有效的邻域搜索方法,以丰富搜索行为;在侦察蜂搜索阶段通过随机搜索对种群进行更新,以增强种群多样性.同时,通过试验设计方法对算法的参数设置进行了分析,给出指导性参数组合.通过基于典型实例的数值仿真以及与已有代表性算法的比较,验证了所提算法的有效性和鲁棒性.     

带不相关并行机和有限缓冲MHFS调度的混合启发式算法

研究每阶段含不相关并行机的多阶段混合流水车间问题(MHFSP),工件的加工时间取决于所分配的机器,相邻阶段之间缓冲区能力有限.鉴于直接求解该NP-hard问题较为困难,将其转化为带阻塞和不相关并行机的MHFSP (BMHFSP-UPM),建立整数规划模型,基于遗传算法(GA)和禁忌搜索(TS)提出一种混合启发式算法(HHGA&TS)进行求解.在该算法中,设计基于多阶段并行加工的二维矩阵编码方案,继而基于二维矩阵元胞组的初始解群体表述设计参数自适应策略;引入基于工件位-基因位的单点倒置交叉以及基于机器号的单点变异过程,利用GA求解机制完成解更新过程;设计机器号次序交换(MNE)、工件位置交换(JNE)、工件工序变异(JNM)三种邻域解移动规则,从而完成基于MNE-JNE-JNM的TS二次优化.仿真实验测试了多达120个工件的720组不同规模实例,结果表明,相较于GA、TS及NEH-IGA,所提出的混合启发式算法在解的质量方面表现更佳.     

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.     

求解异构并行机调度问题的混合多目标教-学优化算法

以异构并行机调度问题为研究对象,考虑了一类以优化总加权完工时间和加权延误总和的调度问题。首先,基于问题描述构建了该问题的混合整数规划模型。其次,提出了混合多目标教-学优化算法。在算法设计中,结合问题的特点设计序列编码方法,并采用分解技术来实现多目标调度问题的求解。此外,该算法通过融合多种交叉算子来定义个体进化过程,并通过与变邻域搜索算法的混合来提升其优化效果。最后,给出了仿真实验与分析,测试结果验证了多目标教-学优化算法求解该调度问题的优越性。