Makespan minimization for scheduling unrelated parallel machines with setup times

This study considers the problem of scheduling jobs on unrelated parallel machines with machine-dependent and job sequence-dependent setup times. In this study, a restricted simulated annealing (RSA) algorithm which incorporates a restricted search strategy is presented to minimize the makespan. The proposed RSA algorithm can effective reduce the search effort required to find the best neighborhood solution by eliminating ineffective job moves. The effectiveness and efficiency of the proposed RSA algorithm is compared with the basic simulated annealing and existing meta-heuristics on a benchmark problem dataset used in earlier studies. Computational results indicate that the proposed RSA algorithm compares well with the state-of-the-art meta-heuristic for small-sized problems, and significantly outperforms basic simulated annealing algorithm and existing algorithms for large-sized problems.     

Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times

A scheduling problem with unrelated parallel machines, sequence and machine-dependent setup times, due dates and weighted jobs is considered in this work. A branch-and-bound algorithm (B&B) is developed and a solution provided by the metaheuristic GRASP is used as an upper bound. We also propose a set of instances for this type of problem. The results are compared to the solutions provided by two mixed integer programming models (MIP) with the solver CPLEX 9.0. We carry out computational experiments and the algorithm performs extremely well on instances with up to 30 jobs.     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

Soft computing for scheduling with batch setup times and earliness-tardiness penalties on parallel machines

A model for scheduling grouped jobs on identical parallel machines is addressed in this paper. The model assumes that a set-up time is incurred when a machine changes from processing one type of component to a different type of component, and the objective is to minimize the total earliness-tardiness penalties. In this paper, the algorithm of soft computing, which is a fuzzy logic embedded Genetic Algorithm is developed to solve the problem. The efficiency of this approach is tested on several groups of random problems and shows that the soft computing algorithm has potential for practical applications in larger scale production systems.     

ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times

To date, the topic of unrelated parallel machine scheduling problems with machine-dependent and job sequence-dependent setup times has received relatively little research attention. In this study, a hybrid artificial bee colony (HABC) algorithm is presented to solve this problem with the objective of minimizing the makespan. The performance of the proposed HABC algorithm was evaluated by comparing its solutions to state-of-the-art metaheuristic algorithms and a high performing artificial bee colony (ABC)-based algorithm. Extensive computational results indicate that the proposed HABC algorithm significantly outperforms these best-so-far algorithms. Since the problem addressed in this study is a core topic for numerous industrial applications, this article may help to reduce the gap between theoretical progress and industrial practice.     

A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines,setup times,and dual criteria

This paper considers a flexible flow shop scheduling problem, where at least one production stage is made up of unrelated parallel machines. Moreover, sequence- and machine-dependent setup times are given. The objective is to find a schedule that minimizes a convex sum of makespan and the number of tardy jobs in a static flexible flow shop environment. For this problem, a 0–1 mixed integer program is formulated. The problem is, however, a combinatorial optimization problem which is too difficult to be solved optimally for large problem sizes, and hence heuristics are used to obtain good solutions in a reasonable time. The proposed constructive heuristics for sequencing the jobs start with the generation of the representatives of the operating time for each operation. Then some dispatching rules and flow shop makespan heuristics are developed. To improve the solutions obtained by the constructive algorithms, fast polynomial heuristic improvement algorithms based on shift moves and pairwise interchanges of jobs are applied. In addition, metaheuristics are suggested, namely simulated annealing (SA), tabu search (TS) and genetic algorithms. The basic parameters of each metaheuristic are briefly discussed in this paper. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages and with an optimal solution for small-size problems. We have found that among the constructive algorithms the insertion-based approach is superior to the others, whereas the proposed SA algorithms are better than TS and genetic algorithms among the iterative metaheuristic algorithms.     

Scheduling jobs on parallel machines with setup times and ready times

In this research we are interested in scheduling jobs with ready times on identical parallel machines with sequence dependent setups. Our objective is to minimize the total weighted tardiness. As this problem is NP-Hard, we develop a heuristic to solve this problem in reasonable time. Our approach is an extension of the apparent tardiness cost with setups (ATCS) approach by [Lee, Y. H., Pinedo, M. (1997). Scheduling jobs on parallel machines with sequence dependent setup times. European Journal of Operational Research, 100, 464–474.] to allow non-ready jobs to be scheduled – meaning we allow a machine to remain idle for a high priority job arriving at a later time. To determine the scaling parameters for our composite dispatching rule (called ATCSR), we first develop a ‘grid approach’ that considers multiple values for the scaling parameters, generates multiple schedules, and chooses the best schedule for the solution. This experimentation was then used to develop regression equations to predict the values of the scaling parameters that would yield the highest quality solution. The grid and regression versions of ATCSR provide better performance than grid and empirically based formula versions of ATCS, BATCS, and X-RM which are the prominent algorithms in the literature.     

A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines,due dates and sequence-dependent setup times

Consider the problem of scheduling a set of jobs to be processed exactly once, on any machine of a set of unrelated parallel machines, without preemption. Each job has a due date, weight, and, for each machine, an associated processing time and sequence-dependent setup time. The objective function considered is to minimize the total weighted tardiness of the jobs.This work proposes a non-delayed relax-and-cut algorithm, based on a Lagrangean relaxation of a time indexed formulation of the problem. A Lagrangean heuristic is also developed to obtain approximate solutions.Using the proposed methods, it is possible to obtain optimal solutions within reasonable time for some instances with up to 180 jobs and six machines. For the solutions for which it is not possible to prove optimality, interesting gaps are obtained.     

A hybrid genetic algorithm for parallel machine scheduling with setup times

Journal of Intelligent Manufacturing - This paper addresses the unrelated parallel machine scheduling problem with sequence and machine dependent setup times and machine eligibility constraints....     

Rescheduling of parallel machines with stochastic processing and setup times

This paper tackles rescheduling for the unrelated parallel machine problem with sequence dependent setup times and different rates of breakdowns or urgent jobs arrivals. The jobs’ processing and setup times are stochastic for better depiction of the real world. A new repair rule which will be referred to as Minimum Weighted C_max Difference (MWCD) is developed and compared to existing algorithms using simulation.     

Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints

This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems.     

Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence-dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on-time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches.     

Online batch scheduling on parallel machines with delivery times

We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m=2 or m=3, respectively. When m≥4, we present an online algorithm with a competitive ratio of 1.5+o(1).     

Unrelated parallel machine scheduling with setup times using simulated annealing

This paper presents a scheduling problem for unrelated parallel machines with sequence-dependent setup times, using simulated annealing (SA). The problem accounts for allotting work parts of L jobs into M parallel unrelated machines, where a job refers to a lot composed of N items. Some jobs may have different items while every item within each job has an identical processing time with a common due date. Each machine has its own processing times according to the characteristics of the machine as well as job types. Setup times are machine independent but job sequence dependent. SA, a meta-heuristic, is employed in this study to determine a scheduling policy so as to minimize total tardiness. The suggested SA method utilizes six job or item rearranging techniques to generate neighborhood solutions. The experimental analysis shows that the proposed SA method significantly outperforms a neighborhood search method in terms of total tardiness.     

带两个服务等级的3台机半在线算法

This paper studies a semi-online hierarchical scheduling problem on three identical machines. In the problem, there is only one machine with hierarchy 1 and two machines with hierarchy 2, and the goal is to minimize the makespan. When the total size of low-hierarchy is known, an online algorithm with the competitive ratio of 5/3 and the lower bound of 3/2 is given. When the total size of high-hierarchy is known, an online algorithm with the competitive ratio of 9/5 and the lower bound of 3/2 is given. When the total size of each hierarchy is known, an online algorithm with the competitive ratio of 3/2 and the lower bound of 4/3 is given. When the total size of jobs is known, a best possible online algorithm with the competitive ratio of 3/2 is given.     

流水车间成组工件调度问题的多目标优化算法

针对优化目标是最小化全部提前/拖期和机器调整次数的多目标流水车间成组工件调度问题,提出了一种改进的变权重进化算法结合延迟调整算法的联合优化方法。首先采用改进的变权重进化算法对加工排序进行寻优;其次,在给定调度序列的情况下采用延迟调整算法对加工时刻进行优化。仿真实验表明,所设计的算法能够有效地求解该类问题。     

Online algorithms for scheduling two parallel machines with a single server

We consider an online scheduling problem on two identical parallel machines with a single server. Jobs arrive one by one and each job has to be loaded by the server before being processed on one of the machines, and unloaded immediately by the server after its processing. Both loading and unloading times are equal to one time unit. The goal is to minimize the makespan. For the variant of the problem involving both loading and unloading operations, we present an online algorithm with competitive ratio of 5/3. For the variant with loading operation only, we show that the competitive ratio of list scheduling is at least 8/5 and provide an improved online algorithm with competitive ratio of 11/7. Finally, we discuss the lower bounds for these problems. We show that both variants have a lower bound of 3/2. Furthermore, we show that the lower bound of the first variant is at least 8/5 if the online algorithm satisfies a certain constraint.     

Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times

This paper considers ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times. Two objects of minimizing the latest job completion time and minimizing the latest machine completion time are studied. For the first objective, we present the optimal algorithms for m = 2, 3, 4 machine cases. For m ≥ 5, we propose an algorithm with competitive ratio 2 - 1/(m - 1) while the lower bound is 5/3. For the second objective, the optimal algorithm is also given. Furthermore, for a special case, an algorithm with significantly improved competitive ratio is given.