On Ashour's decomposition algorithm for shop scheduling problems

This note exposes an oversight in the development of a decomposition approach to the shop scheduling problem reported previously. Included is a brief account of the original algorithm, exposure of its weakness via a small example and a suggested modification.     

Genetic algorithms for job shop scheduling problems with alternative routings

The purpose of this research is to solve a general job shop problem with alternative machine routings. We consider four performance measures: mean flow time, makespan, maximum lateness, and total absolute deviation from the due dates. We first develop mixed-integer linear programming (MILP) formulations for the problems. The MILP formulations can be used either to compute optimal solutions for small-sized problems or to test the performance of existing heuristic algorithms. In addition, we have developed a genetic algorithm that can be used to generate relatively good solutions quickly. Further, computational experiments have been performed to compare the solution of the MILP formulations with that of existing algorithms.     

作业车间调度问题中的协同优化算法

本文采用了多种优化算法 ,针对作业车间问题的特点设计一个比较有效的协同算法 ,解决了算法实现中的几个关键技术问题 ,为提高解决这一问题的效率提供了比较新颖的思路 ,并通过实际计算验证了该方法的可靠性和有效性 ,这一方法可以用于实际车间的调度安排 ,能够提高车间的生产效率。     

Two enhanced differential evolution algorithms for job shop scheduling problems

This paper proposes two new differential evolution algorithms (DE) for solving the job shop scheduling problem (JSP) that minimises two single objective functions: makespan and total weighted tardiness. The proposed algorithms aim to enhance the efficiency of the search by dynamically balancing exploration and exploitation ability in DE and avoiding the problem of premature convergence. The first algorithm allows DE population to simultaneously perform different mutation strategies in order to extract the strengths of various strategies and compensate for the weaknesses of each individual strategy to enhance the overall performance. The second algorithm allows the whole DE population to change the search behaviour whenever the solutions do not improve. This study also introduces a modified local mutation operation embedded in the two proposed DE algorithms to promote exploitation in different areas of the search space. In addition, a local search technique, called Critical Block (CB) neighbourhood, is applied to enhance the quality of solutions. The performances of the proposed algorithms are evaluated on a set of benchmark problems and compared with results obtained from an efficient existing Particle Swarm Optimisation (PSO) algorithm. The numerical results demonstrate that the proposed DE algorithms yield promising results while using shorter computing times and fewer numbers of function evaluations.     

An application of genetic algorithms to lot-streaming flow shop scheduling

A Hybrid Genetic Algorithm (HGA) approach is proposed for a lot-streaming flow shop scheduling problem, in which a job (lot) is split into a number of smaller sublots so that successive operations can be overlapped. The objective is the minimization of the mean weighted absolute deviation of job completion times from due dates. This performance criterion has been shown to be non-regular and requires a search among schedules with intermittent idle times to find an optimal solution. For a given job sequence, a Linear Programming (LP) formulation is presented to obtain optimal sublot completion times. Objective function values of LP solutions are used to guide the HGA's search toward the best sequence. The performance of the HGA approach is compared with that of a pairwise interchange method.     

Performance of decomposition procedures for job shop scheduling problems with bottleneck machines

Decomposition procedures for job shop scheduling problems, such as the shifting bottleneck (SB) procedure, have shown promising results for a variety of shop environments. However, they have primarily been tested using problems where all machines are identical in terms of processing time distribution. Many practical scheduling problems involve bottleneck machines which become the focus of scheduling efforts, as suggested by the theory of constraints. In this paper we examine the performance of several variants of SB, some of which can be interpreted as naive implementations of the TOC approach to scheduling. Our results show that both the solution time and quality of SB methods improve markedly when bottleneck workcentres are present. However, scheduling bottleneck machines optimally and using simple rules at other machines leads to poor performance unless the workload of the bottlenecks significantly exceeds that of the non-bottleneck machines.     

A generalized permutation approach to job shop scheduling with genetic algorithms

In order to sequence the tasks of a job shop problem (JSP) on a number of machines related to the technological machine order of jobs, a new representation technique — mathematically known as permutation with repetition is presented. The main advantage of this single chromosome representation is — in analogy to the permutation scheme of the traveling salesman problem (TSP) — that it cannot produce illegal operation sequences. As a consequence of the representation scheme a new crossover operator preserving the initial scheme structure of permutations with repetition will be sketched. Its behavior is similar to the well known Order-Crossover for simple permutation schemes. Actually theGOX operator for permutations with repetition arises from aGeneralisation ofOX. Computational experiments show, that GOX passes the information from a couple of parent solutions efficiently to offspring solutions. Together, the new representation and GOX support the cooperative aspect of genetic search for scheduling problems strongly.Supported by the Deutsche Forschungsgemeinschaft (Project Parnet)     

Job shop scheduling with delay-renewable resources: A comparison of decomposition strategies

Manufacturing systems are often characterized by the use of resources which need to be 'renewed' after a period of use, such as tools and dies. The resources are not available during their maintenance and if it is too expensive to purchase a suitable number of copies, this may introduce delays and lower the quality of the schedule. We refer to such resources as delay-renewable . In the paper we consider a two-fold generalization of the classical job shop scheduling problem; the operations require the concurrent use of different resources (not only one machine) and the resources are delay-renewable. The resulting scheduling problem is obviously rather difficult and calls for suitable heuristics. A natural way to devise a heuristic approach is to decompose the overall problem into sub-problems and to exploit high-quality meta-heuristics, such as tabu search, for their solution. The purpose of the paper is to discuss and compare two decomposition approaches, differing in the way sub-problems interact, i.e. through constraints and/or information.     

Cultural algorithms,an alternative heuristic to solve the job shop scheduling problem

In this work, an approach for solving the job shop scheduling problem using a cultural algorithm is proposed. Cultural algorithms are evolutionary computation methods that extract domain knowledge during the evolutionary process. Additional to this extracted knowledge, the proposed approach also uses domain knowledge given a priori (based on specific domain knowledge available for the job shop scheduling problem). The proposed approach is compared with respect to a Greedy Randomized Adaptive Search Procedure (GRASP), a Parallel GRASP, a Genetic Algorithm, a Hybrid Genetic Algorithm, and a deterministic method called shifting bottleneck. The cultural algorithm proposed in this article is able to produce competitive results with respect to the two approaches previously indicated at a significantly lower computational cost than at least one of them and without using any sort of parallel processing.     

An optimization-based algorithm for job shop scheduling

Scheduling is a key factor for manufacturing productivity. Effective scheduling can improve on-time delivery, reduce inventory, cut lead times, and improve the utilization of bottleneck resources. Because of the combinatorial nature of scheduling problems, it is often difficult to find optimal schedules, especially within a limited amount of computation time. Production schedules therefore are usually generated by using heuristics in practice. However, it is very difficult to evaluate the quality of these schedules, and the consistency of performance may also be an issue. In this paper, near-optimal solution methodologies for job shop scheduling are examined. The problem is formulated as integer optimization with a “separable” structure. The requirement of on-time delivery and low work-in-process inventory is modelled as a goal to minimize a weighted part tardiness and earliness penalty function. Lagrangian relaxation is used to decompose the problem into individual part subproblems with intuitive appeal. By iteratively solving these subproblems and updating the Lagrangian multipliers at the high level, near-optimal schedules are obtained with a lower bound provided as a byproduct. This paper reviews a few selected methods for solving subproblems and for updating multipliers. Based on the insights obtained, a new algorithm is presented that combines backward dynamic programming for solving low level subproblems and interleaved conjugate gradient method for solving the high level problem. The new method significantly improves algorithm convergence and solution quality. Numerical testing shows that the method is practical for job shop scheduling in industries. This work was supported in part by the National Science Foundation under DMI-9500037, and the Advanced Technology Center for Precision Manufacturing, University of Connecticut.     

Optimal scheduling for flexible job shop operation

This paper presents a new integer linear programming (ILP) model to schedule flexible job shop, discrete parts manufacturing industries that operate on a make-to-order basis. The model considers groups of parallel homogeneous machines, limited intermediate buffers and negligible set-up effects. Orders consist of a number of discrete units to be produced and follow one of a given number of processing routes. The model allows re-circulation to take place, an important issue in practice that has received scant treatment in the scheduling literature. Good solution times were obtained using commercial mixed-integer linear programming (MILP) software to solve realistic examples of flexible job shops to optimality. This supports the claim that recent advances in computational power and MILP solution algorithms are making this approach competitive with others traditionally applied in job shop scheduling.     

Job shop scheduling heuristics and frequency of scheduling

This paper presents a job scheduling problem. Two important aspects are included in the subsequent analysis. The first is the dynamic nature whereby new jobs arrive to be included intermittently through time. The second is the uncertainty, or error in estimating process times, and the likelihood of machine breakdown. An experiment is presented which shows the performance of a number of heuristics in the form of dispatching disciplines under different scheduling conditions which are determined by the scheduling period and the level of uncertainty in the process times and machine breakdowns. Various different measures of performance which could be of importance to management are considered. These include mean ratio of flow time to process time, mean queueing time, mean lateness, percentage of jobs late and net CPU times required to generate schedules in the simulation process.

Results are presented showing the relationship between the performance of the heuristics relative to the different measures and the rescheduling period. These are discussed in the more general managerial context.     

Seqential approach in job shop scheduling

Abstract

This study investigats a new approach‐the sequential approach‐ in job shop scheduling. The objective is to minimize the total of lateness cost and set‐up cost in job shops. Whenever a scheduling decision has to be made as to which job should receive the next processing, this approach considers each cost sequentially. One of the two costs is considered first, and every time all waiting jobs must be examined in terms of this cost, and only those jobs qualified would the second cost apply to and from which a job would be selected for processing. This investigation was carried out by using GASP IV simulation under a variety of job shop situations. The effectiveness of this approach and job selection mechanism constitute the main theme of this study.     

Multi-objective genetic algorithm for energy-efficient job shop scheduling

The paper investigates the effects of production scheduling policies aimed towards improving productive and environmental performances in a job shop system. A green genetic algorithm allows the assessment of multi-objective problems related to sustainability. Two main considerations have emerged from the application of the algorithm. First, the algorithm is able to achieve a semi-optimal makespan similar to that obtained by the best of other methods but with a significantly lower total energy consumption. Second, the study demonstrated that the worthless energy consumption can be reduced significantly by employing complex energy-efficient machine behaviour policies.     

Time- and cost-based priorities for job shop scheduling

Competitively, cost- and time-based scheduling should provide a firm with a powerful market advantage. The cost- and time-based priority scheduling concept is driven by profit maximization and quick response in a competitive market. The literature on shop scheduling contains numerous studies reporting on the use of dispatching rules that are based only on the time criterion. Alternatively there have been only a few published articles that specifically consider a composite of cost and time. Aggarwal and McCarl and Scudder and Hoffmann have investigated the use of cost and time information for determining the job priority in random job shops. One result of this study is a reconciliation of the differences between the Aggarwal and McCarl and the Scudder and Hoffmann study. Moreover, a simplistic priority rule based on profit margin and due dates is introduced and tested. The results reported in this research are an attempt to reconcile the issue of time-based versus cost-based priority rule performance.     

Twofold look-ahead search for multi-criterion job shop scheduling

The twofold look-ahead search ((TLAS) was proposed as a general purpose search technique and applied to single-criterion job shop scheduling. In the present study, this method is applied to multi-criterion scheduling problems with some modification and illustrated by bi-criterion scheduling with mean tardiness and mean flowtime. Application circumstances are divided into two situations according to the scheduling objective and TLAS is tested for each situation. From the computational results, the proposed method is found to generate higher performance schedules in comparison with other methods. Its algorithmic features and applicability to other problems are also discussed based on several experimental results.     

Project scheduling algorithms for re-layout projects

The most common type of facility layout project is re-layout, which involves rearranging existing equipment in a facility. Project schedule development is an often overlooked yet critical portion of a facility re-layout project. When developing a re-layout project schedule, departments cannot be moved into their final locations until all previous occupants have moved. By incurring the cost of moving departments to temporary locations, it is possible to reduce the overall project duration. A two-criteria mixed-integer programming model is developed that finds the schedule minimizing department move costs subject to precedence constraints. An efficient algorithm uses this model to find all non-dominated time and cost solutions to the re-layout problem. Modifications to the basic model and algorithm handle resource constraints and turnaround space constraints. The algorithm and its modifications are demonstrated on an actual re-layout project.     

Project scheduling algorithms for re-layout projects

The most common type of facility layout project is re-layout, which involves rearranging existing equipment in a facility. Project schedule development is an often overlooked yet critical portion of a facility re-layout project. When developing a re-layout project schedule, departments cannot be moved into their final locations until all previous occupants have moved. By incurring the cost of moving departments to temporary locations, it is possible to reduce the overall project duration. A two-criteria mixed-integer programming model is developed that finds the schedule minimizing department move costs subject to precedence constraints. An efficient algorithm uses this model to find all non-dominated time and cost solutions to the re-layout problem. Modifications to the basic model and algorithm handle resource constraints and turnaround space constraints. The algorithm and its modifications are demonstrated on an actual re-layout project.     

Integer programming models for the re-entrant shop scheduling problems

A re-entrant shop describes a manufacturing environment in which a machine can process a job more than once. A re-entrant shop can be classified into a re-entrant job-shop (RJS) and a re-entrant flow-shop (RFS). This article presents the development of the mixed binary integer programming (BIP) technique for the RJS and the RFS scheduling problems. Eight mixed BIP models are proposed for solving re-entrant shop scheduling problems to minimize makespan. The models RJS-1, RJS-2, RJS-3, and RJS-4 are for the RJS problems, while the other four models (RFS-1, RFS-2, RFS-3, and RFS-4) are for the RFS problems. Computational results show that the RJS-4 model is the best of the RJS models, and the RFS-3 model is the best of the RFS models.     

An improved multi-objective evolutionary algorithm based on decomposition for energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time

With the increasing attention on environment issues, green scheduling in manufacturing industry has been a hot research topic. As a typical scheduling problem, permutation flow shop scheduling has gained deep research, but the practical case that considers both setup and transportation times still has rare research. This paper addresses the energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time to minimise both makespan as economic objective and energy consumption as green objective. The mathematical model of the problem is formulated. To solve such a bi-objective problem effectively, an improved multi-objective evolutionary algorithm based on decomposition is proposed. With decomposition strategy, the problem is decomposed into several sub-problems. In each generation, a dynamic strategy is designed to mate the solutions corresponding to the sub-problems. After analysing the properties of the problem, two heuristics to generate new solutions with smaller total setup times are proposed for designing local intensification to improve exploitation ability. Computational tests are carried out by using the instances both from a real-world manufacturing enterprise and generated randomly with larger sizes. The comparisons show that dynamic mating strategy and local intensification are effective in improving performances and the proposed algorithm is more effective than the existing algorithms.