In this paper, the flow shop with blocking and sequence and machine dependent setup time problem aiming to minimize the makespan is studied. Two mixed-integer programming models are proposed (TNZBS1 and TNZBS2) and two other mixed-integer programming models, originally proposed for the no setup problem, are adapted to the problem. Furthermore, an Iterated Greedy algorithm is proposed for the problem. The permutation flow shop with blocking and sequence and machine dependent setup time is an underexplored problem and the authors did not find the use of mixed-integer programming models for the problem in any other work. To compare the models, a database of 80 problems was generated, which vary in number of machines and jobs. For the small sized problems, the adapted MILP model obtained the best results. However, for bigger problems, both proposed MILP models obtained significantly better results compared to the adapted models, proving the efficiency of the new models. When comparing the Iterated Greedy algorithm with the MILP models, the former outperformed the latter.

The literature on flow shop scheduling has extensively analyzed two classes of problems: permutation and non-permutation ones (PFS and NPFS). Most of the papers in this field have been just devoted on comparing the solutions obtained in both approaches. Our contribution consists of analyzing the structure of the critical paths determining the makespan of both kinds of schedules for the case of 2 jobs and m machines. We introduce a new characterization of the critical paths of PFS solutions as well as a decomposition procedure, yielding a representation of NPFS solutions as sequences of partial PFS ones. In structural comparisons we find cases in which NPFS solutions are dominated by PFS solutions. Numerical comparisons indicate that a wider dispersion of processing times improves the chances of obtaining optimal non-permutation schedules, in particular when this dispersion affects only a few machines.

The processing time of the machine is assumed fixed in several studies. In many real industrial applications, the processing time is affected by learning and forgetting effects. This research proposes a scheduling approach to support a manufacturing system under learning/forgetting effect. The approach is supported by a Multi-Agent System to perform the scheduling activities in a quasi-real-time and in general manufacturing systems. A simulation environment is developed to test the proposed approach and the results are compared with a benchmark model for evaluating several performance measures of the manufacturing system. The simulation results highlight how the proposed approach improves all the performance measures under different conditions of inter-arrival time, learning and forgetting rates. A complete Analysis of the Variance highlights the main effects on the performance measures to support the decision maker of the manufacturing system.

Flow shop scheduling problems with rudimentary criteria of minimum makespan are the most important investigated problems in the field of scheduling. Generally during the process of generating an optimal sequence, multiple partial sequences claiming the optimal value of makespan are observed. In this paper a novel tie-breaking rule to select one of the best optimal sequences out of all possible partial sequences is developed which then applied to Nawaz-Enscore-Ham (NEH) heuristic to solve the scheduling problems in permutation flowshop without increasing the computational complexity. The performance of proposed heuristic is tested with other existing tie-breaking heuristics of similar complexity over Taillard and VRF's instances. Computational results reveal that in terms of solution quality, the proposed heuristic outperforms over the other NEH based heuristics of the same complexity reported in literature.

Additive Manufacturing (AM) is a process of joining materials to make objects from 3D model data, usually layer by layer, as opposed to subtractive manufacturing methodologies. Selective Laser Melting, commercially known as Direct Metal Laser Sintering (DMLS®), is the most diffused additive process in today’s manufacturing industry. Introduction of a DMLS® machine in a production department has remarkable effects not only on industrial design but also on production planning, for example, on machine scheduling. Scheduling for a traditional single machine can employ consolidated models. Scheduling of an AM machine presents new issues because it must consider the capability of producing different geometries, simultaneously. The aim of this paper is to provide a mathematical model for an AM/SLM machine scheduling. The complexity of the model is NP-HARD, so possible solutions must be found by metaheuristic algorithms, e.g., Genetic Algorithms. Genetic Algorithms solve sequential optimization problems by handling vectors; in the present paper, we must modify them to handle a matrix. The effectiveness of the proposed algorithms will be tested on a test case formed by a 30 Part Number production plan with a high variability in complexity, distinct due dates and low production volumes.

In recent years, many studies on the multi-agent scheduling problems in which agents compete for using the shared resources, have been performed. However, relatively few studies have been undertaken in the field of the multi-agent scheduling in a flowshop environment. To bridge the gap, this paper aims at addressing the two-agent scheduling problem in a two-machine flowshop. Because of the importance of delay penalties and efficient resource utilization in many manufacturing environments, the objective is to find an optimal schedule which has the minimum total tardiness for the first agent’s jobs, under the makespan limitation for the second agent. Since this problem is strongly NP-hard, several theorems and properties of the problem are proposed to apply in exact and meta-heuristic methods. Also, for some instances of the problem for which exact methods cannot achieve optimal solutions in a reasonable amount of time, a tabu search algorithm is developed to achieve near-optimal solutions. Computational results of the tabu search algorithm show that the average absolute error value is lower than 0.18 percent for instances with 20 to 60 jobs in size.

This paper focuses on the problem of scheduling and routing workers in a courier service to deliver packages for a set of geographically distributed customers and, on a specific date and time window. The crew of workers has a limited capacity and a time window that represents their labor length. The problem deals with a combination of multiples variants of the vehicle routing problem as capacity, multiple periods, time windows, due dates and distance as constraints. Since in the courier services the demands could be of hundreds or thousands of packages to be delivered, the problem is computationally unmanageable. We present a three-phase solution approach. In the first phase, a scheduling model determines the visit date for each customer in the planning horizon by considering the release date, due date to visit and travel times. We use an expert system based on the know-how of the courier service, which uses an inference engine that works as a rule interpreter. In the second phase, a clustering model assigns, for each period, customers to workers according to the travel times, maximum load capacity and customer’s time windows. We use a centroid based and sweep algorithms to solve the resulted problem. Finally, in the third phase, a routing model finds the order in which each worker will visit all customers taking into account their time windows and worker’s available time. To solve the routing problem we use an Ant Colony Optimization metaheuristic. We present some numerical results using a case study, in which the proposed method of this paper finds better results in comparison with the current method used in the case study.

The current paper investigates a two-stage flow shop scheduling model with no idle restriction, in which the time taken by machines to set-up is separately considered from the processing time. Owing to inherent usefulness as well as relevance in real-world situations, jobs' weight has additionally included. To eliminate machine idle time and cutting machine cost of rental, the reason for the conduct of the study is to provide a heuristic algorithm which, once put into practice, processes jobs in an optimal way, guarantees in smallest conceivable make span. Multiple computational examples generated in MATLAB 2019a serve as testament to the efficacy of the proposed strategy. The outcomes are contrasted with the current methods that Johnson, Palmer and NEH have demonstrated.

To better meet the qualitative and quantitative requirements of customers or relevant sector managers, workshop environments are implementing increasingly complex task management systems. The job shop scheduling problem (JSSP) involves assigning each task to a single machine while scheduling many tasks on different machines. Finding the best scheduling for machines is one of the challenging optimizations of difficult non-deterministic polynomial (NP) time problems. The fundamental goal of optimization is to shorten the makespan (total execution time of all tasks). This paper is interested in the joint resolution of scheduling and transport problems and more particularly the Job-shop problem with Routing (JSSPR) as opposed to the Job-shop problem with Transport (JSSPT). These two problems are modeled in the form of a disjunctive graph. For the JSSPT, the solution to the transport problem is not linked to any quality of service (QoS) criterion and the solution is therefore often semi-active. The Job-shop with Routing explicitly considers transport operations and uses algorithms from the transport community to solve the transport problem. It is shown that the routing part of the JSSPR is a problem of the vehicle routing family and of the Pickup and Delivery Problem family. QoS in the JSSPR is defined by the duration of tours, the duration of transport of parts and the waiting time for them. A new evaluation function – named Time-Lag Insertion Heuristic (TLH) – is proposed to evaluate a disjunctive graph by simultaneously minimizing the makespan and maximizing the quality of service. Thus, the solution obtained is not semi-active, but a compromise between the different criteria. This evaluation function is included in a metaheuristic. Our numerical evaluations demonstrate that, on the one hand, the TLH evaluation can find almost optimal solutions regarding the QoS criterion; and on the other hand, the TLH evaluation is not very sensitive to the order of insertion of the maximum time-lags during the different minimization steps.

This paper addresses the flexible manufacturing system (FMS) problems considering both machines and automated guided vehicles (AGVs), simultaneously. A new fuzzy heuristic (FH) is proposed for solving the simultaneous scheduling problem, in order to minimize the makespan by considering the available resources. For increasing the performance of FMS one of the important factors is scheduling AGV with an integral part of the machine scheduling activity. The algorithm is tested based on 82 benchmark problems and the achieved makespan are compared with other algorithms.