Some effective heuristics for no-wait flowshops with setup times to minimize total completion time

In this work, we consider a complex flowshop scheduling problem in which both no-wait and separate setup times are considered. The optimisation criterion is the minimisation of the total completion time. We propose an effective dominance rule for the four machine case that can also be used for m machines. Five simple and fast heuristics are proposed along with two easy to code stochastic local search methods, one of them being based on Iterated Local Search (ILS). An extensive computational evaluation is carried out with two sets of 5,400 instances. All seven methods are compared to two recent algorithms. The results, confirmed by thorough statistical analyses, show that the proposed methods are more effective and efficient when compared to the best existing algorithms in the literature for the considered problem.     

Batch arrival queues with vacations and server setup

We study a single server queueing system whose arrival stream is compound Poisson and service times are generally distributed. Three types of idle period are considered: threshold, multiple vacations, and single vacation. For each model, we assume after the idle period, the server needs a random amount of setup time before serving. We obtain the steady-state distributions of system size and waiting time and expected values of the cycle for each model. We also show that the distributions of system size and waiting time of each model are decomposed into two parts, whose interpretations are provided. As for the threshold model, we propose a method to find the optimal value of threshold to minimize the total expected operating cost.     

一个单机分批排序问题的算法以及Java实现

该文讨论了一类新的排序问题---和资源相关的排序问题,介绍了该类问题的一些概念,探讨了一些算法并用Java进行了模拟测试     

Optimal transportation policies for production/inventory systems with an unreliable and a reliable carrier

In this paper, we consider a periodic-review make-to-order production/inventory system with two outbound transportation carriers: One carrier is reliable, the other carrier is less reliable but more economical. The objective is to find the optimal shipping policy that minimizes the total discounted transportation, inventory, and customer waiting costs. Under several scenarios, we characterize the optimal policy and present the structural properties for the optimal control parameters and the key performance measures. Our results provide managerial insights on how a manufacturer can effectively manage its transportation carriers and product shipment. We also discuss several possible extensions of the model.     

Controlling setup cost in (Q, r, L) inventory model with defective items

This study discusses a mixture inventory model with back orders and lost sales in which the order quantity, reorder point, lead time and setup cost are decision variables. It is assumed that an arrival order lot may contain some defective items and the number of defective items is a random variable. There are two inventory models proposed in this paper, one with normally distributed demand and another with distribution free demand. Finally we develop two computational algorithms to obtain the optimal ordering policy. A computer code using the software Matlab is developed to derive the optimal solution and present numerical examples to illustrate the models. Additionally, sensitivity analysis is conducted with respect to the various system parameters.     

A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations

A hybrid flow shop scheduling problem (HFSP) with assembly operations is studied in this paper. In the considered problem, a number of products of the same kind are produced. Each product is assembled using a set of several parts. At first, the parts are produced in a hybrid flow shop and then they are assembled in an assembly stage to produce products. The considered objective is to minimize the completion time of all products (makespan). This problem has been proved strongly NP-hard, so in order to solve it, a hierarchical branch and bound algorithm is presented. Also, some lower and upper bounds are developed to increase the efficiency of the proposed algorithm. The numerical experiments are used to evaluate the performance of the proposed algorithm.     

Total completion time with makespan constraint in no-wait flowshops with setup times

The m-machine no-wait flowshop scheduling problem with the objective of minimizing total completion time subject to the constraint that the makespan value is not greater than a certain value is addressed in this paper. Setup times are considered non-zero values, and thus, setup times are treated as separate from processing times. Several recent algorithms, an insertion algorithm, two genetic algorithms, three simulated annealing algorithms, two cloud theory-based simulated annealing algorithms, and a differential evolution algorithm are adapted and proposed for the problem. An extensive computational analysis has been conducted for the evaluation of the proposed algorithms. The computational analysis indicates that one of the nine proposed algorithms, one of the simulated annealing algorithms (ISA-2), performs much better than the others under the same computational time. Moreover, the analysis indicates that the algorithm ISA-2 performs significantly better than the earlier existing best algorithm. Specifically, the best performing algorithm, ISA-2, proposed in this paper reduces the error of the existing best algorithm in the literature by at least 90% under the same computational time. All the results have been statistically tested.     

Grasp with memory-based mechanisms for minimizing total tardiness in single machine scheduling with setup times

This paper addresses the problem of scheduling jobs in a single machine with sequence dependent setup times in order to minimize the total tardiness with respect to job due dates. We propose variants of the GRASP metaheuristic that incorporate memory-based mechanisms for solving this problem. There are two mechanisms proposed in the literature that utilize a long-term memory composed of an elite set of high quality and sufficiently distant solutions. The first mechanism consists of extracting attributes from the elite solutions in order to influence the construction of an initial solution. The second one makes use of path relinking to connect a GRASP local minimum with a solution of the elite set, and also to connect solutions from the elite set. Reactive GRASP, which probabilistically determines the degree of randomness in the GRASP construction throughout the iterations, is also investigated. Computational tests for instances involving up to 150 jobs are reported, and the proposed method is compared with heuristic and exact methods from the literature.     

Competitive online scheduling of perfectly malleable jobs with setup times

We study how to efficiently schedule online perfectly malleable parallel jobs with arbitrary arrival times on m ? 2 processors. We take into account both the linear speedup of such jobs and their setup time, i.e., the time to create, dispatch, and destroy multiple processes. Specifically, we define the execution time of a job with length p_j running on k_j processors to be p_j/k_j + (k_j − 1)c, where c > 0 is a constant setup time associated with each processor that is used to parallelize the computation. This formulation accurately models data parallelism in scientific computations and realistically asserts a relationship between job length and the maximum useful degree of parallelism. When the goal is to minimize makespan, we show that the online algorithm that simply assigns k_j so that the execution time of each job is minimized and starts jobs as early as possible has competitive ratio 4(m − 1)/m for even m ? 2 and 4m/(m + 1) for odd m ? 3. This algorithm is much simpler than previous offline algorithms for scheduling malleable jobs that require more than a constant number of passes through the job list.     

最小化延误工序的单机限期批处理问题(英文)

本文讨论了最小化延误工序的单机限期批处理问题，并对当所有工序同时处理时的特例给出了两个多项式算法．