带学习效应的两台平行机时间表长问题

研究机器带学习效应, 目标函数为时间表长的两台平行机排序问题, 问题是NP-难的. 首先建立了求解该问题最优解的整数规划模型. 其次, 基于模拟退火算法给出了该问题的近似算法SA, 并证明了该算法依概率1 全局收敛到最优解. 最后, 通过数值模拟对所提出的算法进行了性能分析. 数值模拟结果表明, 近似算法SA可以达到最优值的99%, 准确度高, 算法较有效.     

Minimizing makespan in re-entrant permutation flow-shops

A re-entrant flow-shop (RFS) describes situations in which every job must be processed on machines in the order of M₁, M₂, …, M _m , M₁, M₂, …,M _m , …, and M₁, M₂, …,M _m . In this case, every job can be decomposed into L levels and each level starts on M₁, and finishes on M _m . In a RFS case, if the job ordering is the same on any machine at each level, then it is said that no passing is allowed since any job is not allowed to pass any previous job. The RFS scheduling problem where no passing is allowed is called the re-entrant permutation flow-shop (RPFS) problem. This paper proposes three extended mixed BIP formulations and six extended effective heuristics for solving RPFS scheduling problems to minimize makespan.     

Minimizing makespan for two parallel machines with job limit on each availability interval

We consider the problem of scheduling jobs on two parallel machines that are not continuously available for processing. The machine is not available after processing a fixed number of jobs in order to make precision adjustment of machines such as in wafer manufacturing, to reload the feeder in printed circuit board production, or to undertake any other maintenance works such as cleaning and safety inspections. The objective of the problem is to minimize the makespan. Two different scheduling horizons are investigated for this problem. For the short-term scheduling horizon, we consider only the time period before the unavailability interval, while for the long-term horizon, machines are allowed to restart processing after the unavailability interval. For both cases, which are strongly NP-hard, exact optimization algorithms based on the branch and bound method are proposed. Although the algorithms have exponential time complexities, computational results show that they can solve optimally the various-sized problems in reasonable computation time.     

No-wait flowshops with bicriteria of makespan and total completion time

We consider the m-machine no-wait flowshop scheduling problem with the objective of minimizing a weighted sum of makespan and total completion time. For the two-machine problem, we develop a dominance relation and embed it within a proposed branch-and-bound algorithm. For the m-machine problem, we propose a heuristic. Computational experiments show that the proposed heuristic outperforms the best existing multi-criteria heuristics and the best single criterion heuristics for makespan and total completion time. The efficiency of the dominance relation and branch-and-bound algorithm is also investigated and shown to be effective.     

Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes

This paper considers the scheduling problem of parallel batch processing machines with non-identical job sizes. The jobs are processed in batches and the machines have the same capacity. The models of minimizing makespan and total completion time are given using mixed integer programming method and the computational complexity is analyzed. The bound on the number of feasible solutions is given and the properties of the optimal solutions are presented. Then a polynomial time algorithm is proposed and the worst case ratios for minimizing total completion time and makespan is proved to be 2 and (8/3–2/3 m) respectively. To test the proposed algorithm, we generate different levels of random instances. The computational results demonstrate the effectiveness of the algorithm for minimizing the two objectives.     

Minimizing makespan with multiple-orders-per-job in a two-machine flowshop

We investigate a new scheduling problem, multiple-orders-per-job (MOJ), in the context of a two-machine flowshop. Lower bounds for the makespan performance measure are provided for combinations of lot-processing and item-processing machines. An optimization model is presented that addresses both job formation and job sequencing. We define a heuristic to minimize the makespan for the MOJ problem for two-machine item-processing flowshops. The heuristic obtains solutions within 2% of a tight lower bound and runs in O(HF) time, where H is the number of orders and F is the restricted number of jobs.     

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.     

Minimizing makespan on a two-machine re-entrant flowshop

This paper focuses on a two-machine re-entrant flowshop scheduling problem with the objective of minimizing makespan. In the re-entrant flowshop considered here, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2. We develop dominance properties, lower bounds and heuristic algorithms for the problem, and use these to develop a branch and bound algorithm. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 200 jobs in a reasonable amount of CPU time.     

Minimizing makespan on a single burn-in oven in semiconductor manufacturing

This paper considers a scheduling problem for a single burn-in oven in semiconductor manufacturing industry where the oven is a batch processing machine and each batch processing time is represented by the largest processing time among those of all the jobs contained in the batch. The objective measure of the problem is the maximum completion time (makespan) of all jobs. This paper investigates a static case in which all jobs are available to process at time zero, and also analyzes a dynamic case with different job-release times, for which a branch-and-bound algorithm and several heuristics are exploited. The worst case error performance ratios of the heuristics are also derived.     

Minimizing the makespan in a two-machine cross-docking flow shop problem

This paper studies a two-machine cross-docking flow shop scheduling problem in which a job at the second machine can be processed only after the processing of some jobs at the first machine has been completed. The objective is to minimize the makespan. We first show that the problem is strongly NP-hard. Some polynomially solvable special cases are provided. We then develop a polynomial approximation algorithm with an error-bound analysis. A branch-and-bound algorithm is also constructed. Computational results show that the branch-and-bound algorithm can optimally solve problems with up to 60 jobs within a reasonable amount of time.     

Minimizing makespan and throughput times at Aalsmeer flower auction

At Bloemenveiling Aalsmeer (VBA), about 19 million flowers have to be distributed daily to customers in a building of 1 million?m² within a few hours. With the increasing daily number of customer orders, the congestion in the main distribution area increases. As a consequence, the makespan exceeds the available time, and flowers arrive too late at the customers. This paper investigates the concept of zoning in the distribution process, where distributors work in teams for a fixed group of customers in a specific zone of the distribution area. Customers are assigned to zones to balance workload. We show by simulation that this way of organizing the distribution process reduces congestion and leads to considerable improvements in both makespan and transaction lead time.     

Minimizing energy consumption and makespan in a two-machine flowshop scheduling problem

Energy consumption has become a key concern for manufacturing sector because of negative environmental impact of operations. We develop constructive heuristics and multi-objective genetic algorithms (MOGA) for a two-machine sequence-dependent permutation flowshop problem to address the trade-off between energy consumption as a measure of sustainability and makespan as a measure of service level. We leverage the variable speed of operations to develop energy-efficient schedules that minimize total energy consumption and makespan. As minimization of energy consumption and minimization of makespan are conflicting objectives, the solutions to this problem constitute a Pareto frontier. We compare the performance of constructive heuristics and MOGAs with CPLEX and random search in a wide range of problem instances. The results show that MOGAs hybridized with constructive heuristics outperform regular MOGA and heuristics alone in terms of quality and cardinality of Pareto frontier. We provide production planners with new and scalable solution techniques that will enable them to make informed decisions considering energy consumption together with service objectives in shop floor scheduling.     

Minimizing makespan on a single machine subject to random breakdowns

We investigate optimal sequencing policies for the expected makespan problem with an unreliable machine, where jobs have to be reprocessed in their entirety if preemptions occur because of breakdowns. We identify a class of uptime distributions under which LPT minimizes expected makespan.     

Minimizing makespan in a two-machine flowshop scheduling with batching and release time

This paper studies two-machine flowshop scheduling with batching and release time, whose objective is to minimize the makespan. We formulate the scheduling problem as a mixed integer programming model and show that it is a strongly NP-hard problem. We derive a lower bound and develop dynamic programming-based heuristic algorithms to solve the scheduling problem. Computational experiments are carried out to evaluate the performance of the heuristic algorithms. The numerical results show that some of the heuristic algorithms can indeed find effective solutions for the scheduling problem.     

A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs

In this paper, we consider the problem of permutation flowshop scheduling with the objectives of minimizing the makespan and total flowtime of jobs, and present a Multi-Objective Simulated-annealing Algorithm (MOSA). Two initial sequences are obtained by using simple and fast existing heuristics, supplemented by the implementation of three improvement schemes. Each of the two resultant sequences corresponds to a possible non-dominated solution containing the minimum value of one objective function. These sequences, taken one at a time, are given as the starting sequences to the MOSA. The MOSA seeks to obtain non-dominated solutions through the implementation of a simple probability function that attempts to generate solutions on the Pareto-optimal front. The probability function selects probabilistically a particular objective function, considering which the algorithm uncovers non-dominated solutions. Moreover, the probability function is varied in such a way that the entire objective-function space is covered uniformly so as to obtain as many non-dominated and well-dispersed solutions as possible. The parameters in the proposed MOSA are determined after conducting a pilot study. Two variants of the proposed algorithm, called MOSA-I and MOSA-II, with different parameter settings with respect to the temperature and epoch length, are considered in the performance evaluation of algorithms. In order to evaluate MOSA-I and MOSA-II, we have made use of 90 benchmark problems provided by Taillard [Eur. J. Operation. Res. 64 (1993) 278]. After an extensive literature survey, the following flowshop multi-objective scheduling algorithms have been identified as benchmark procedures: (a) MOGLS (Multi-Objective Genetic Local Search) by Ishibuchi and Murata [IEEE Trans. Syst., Man, Cybernet. C: Appl. Rev. 28 (1998) 392]; (b) Elitist Non-dominated sorting Genetic Algorithm (ENGA) by Bagchi [Multi-Objective Scheduling by Genetic Algorithms, Kluwer Academic Publishers, 1999]; (c) GPW (Gradual Priority Weighting) approach by Chang, Hsieh and Lin [Int. J. Prod. Econ. 79 (2002) 171]; and (d) a posteriori approach based heuristic by Framinan, Leisten and Ruiz-Usano [Eur. J. Operation. Res. 141 (2002) 559]. The non-dominated sets obtained from each of the existing benchmark algorithms and the proposed MOSA-I and MOSA-II are compared, and subsequently combined to obtain a net non-dominated front. It is found that most of the solutions in the net non-dominated front are yielded by MOSA-I and MOSA-II. In addition, it is noteworthy that both MOSA-I and MOSA-II require less computational effort than the MOGLS, ENGA and GPW.     

Performance of scheduling algorithms for no-wait flowshops with parallel machines

We study the performance of scheduling algorithms for a manufacturing system, called the ‘no-wait flowshop’, which consists of a certain number of machine centers. Each center has one or more identical parallel machines. Each job is processed by at most one machine in each center. The problem of finding the minimum finish time schedule is considered here in a flowshop consisting of two machine centers. Heuristic algorithms are presented and are analyzed in the worst case performance context. For the case of two centers, one with a single machine and the other with m, two heuristics are presented with tight performance guarantees of 3 − (1/m) and 2. When both centers have m machines, a heuristic is presented with an upper bound performance guarantee of . It is also shown that this bound can be reduced to 2(1 + ε). For the flowshop with any number of machines in each center, we provide a heuristic algorithm with an upper bound performance guarantee that depends on the relative number of machines in the centers.     

Minimizing makespan in a two-machine flow shop with effects of deterioration and learning

We consider a two-machine flow shop scheduling problem with effects of deterioration and learning. By the effects of deterioration and learning, we mean that the processing time of a job is a function of its execution starting time and its position in a sequence. The objective is to find a sequence that minimizes the makespan. Several dominance properties and two lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm proposed to solve the problem. Two heuristic algorithms are also proposed to obtain near-optimal solutions. Computational results are presented to evaluate the performance of the proposed algorithms.     

Minimizing the makespan in a 2-machine flowshop with time lags and setup conditions

A special case of the flowshop problem of sequencingn jobs on two machines, to minimize the makespan, is solved under setup considerations and with time lags.

---

Zusammenfassung In dieser Arbeit wird die Minimierung der Fertigstellungsdauer vonn Aufträgen auf 2 Maschinen behandelt, wobei auch Umrüstzeiten für die Maschinen und Aufbereitungszeiten für die Aufträge in Betracht gezogen werden.

     

Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance

This paper deals with a single machine scheduling problems with availability constraints. The unavailability of machine results from periodic maintenance activities. In our research, a periodic maintenance consists of several maintenance periods. We consider a machine should stop to maintain after a periodic time interval or to change tools after a fixed amount of jobs processed simultaneously. Each maintenance period is scheduled after a periodic time interval. We study the problems under deterministic environment and flexible maintenance considerations. Preemptive operation is not allowed. In addition, we propose a more reasonable flexible model for the real production settings. The objective is to minimize the makespan. The proposed problem is NP-hard in the strong sense and some heuristic algorithms are provided. The purpose is to present an efficient and effective heuristic algorithm so that it will be straightforward and easy to implement. Computational results show that the proposed algorithm first fit decreasing (DFF) performs well.     

Unbounded parallel batch scheduling with job delivery to minimize makespan

We consider unbounded parallel batch scheduling with job delivery to minimize makespan. When the jobs have identical size, we provide a polynomial-time algorithm. When the jobs have non-identical sizes, we provide a heuristic with a worst-case performance ratio 7/4.