A block transportation scheduling system considering a minimisation of travel distance without loading of and interference between multiple transporters

Material transportation scheduling problems concerning scheduling optimisation have been extensively investigated by researchers in such fields as industrial engineering and management science. Various algorithms have been proposed to solve such problems. However, the majority of these algorithms cannot be applied to a block transportation problem when a shipyard that uses a transporter, a large vehicle employed for moving weight, is considered. In this study, a hybrid optimisation algorithm is proposed for solving a block transportation problem when multiple transporters are used. With regards to the transporters, a minimisation of the travel distance without loading of and interference between the transporters is considered. A block transportation scheduling system is then developed based on the proposed algorithm. The developed system is applied to an actual block transportation scheduling problem of a shipyard. From the attained results, we demonstrate that the proposed algorithm has the ability to effectively solve the block transportation scheduling problems of a shipyard.     

A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness

This paper addresses a real-life production scheduling problem with identical parallel machines, originating from a plant producing Acrylonitrile-Butadiene-Styrene (ABS) plate products. In the considered practical scheduling problem, ABS plate has some specific specifications and each specification has several different levels. Because there is at least one different level of specification between two ABS plate products, it is necessary to make a set-up adjustment on each machine whenever a switch occurs from processing one ABS plate product to another product. As tardiness leads to extra penalty costs and opportunity losses, the objective of minimising total tardiness has become one of the most important tasks for the schedule manager in the plant. The problem can be classified as an identical parallel machine scheduling problem to minimise the total tardiness. A dispatching rule is proposed for this problem and evaluated by comparing it with the current scheduling method and several existing approaches. Moreover, an iterated greedy-based metaheuristic is developed to further improve the initial solution. The experimental results show that the proposed metaheuristic can perform better than an existing tabu search algorithm, and obtain the optimal solution for small-sized problems and significantly improve the initial solutions for large-sized problems.     

A coordinated algorithm for integrated production scheduling and vehicle routing problem

In this paper, the integrated production scheduling and vehicle routing problem is considered for a Make-to-Order manufacturer, who has a single machine for production and limited vehicles with capacity constraints for transportation. The objective is to determine production scheduling and vehicle routing, which are two interacted decisions, to minimise the maximum order delivery time. A property on optimal production sequence is proposed first, based on which backward and forward batching methods are developed and are embedded into a proposed genetic algorithm. The proposed genetic algorithm is capable of providing high-quality solutions by determining the two decisions simultaneously. For comparison purpose, a two-stage algorithm is developed, which decomposes the overall problem into two successively solved sub-problems. The experiments show that the proposed genetic algorithm can provide higher quality solutions than the proposed two-stage algorithm and two published algorithms studying related problems.     

New block properties for flowshop scheduling with blocking and their application in an iterated greedy algorithm

This paper proposes new block properties for the flowshop scheduling problem with blocking to minimise makespan. A pruning procedure based on these proposed properties is used in the construction phase of an iterated greedy algorithm to decrease the total number of solutions to be examined to find an optimal schedule. Computational results using Taillard’s benchmark problem instances show that the new block properties help to eliminate more ‘unpromising’ solutions than the classic properties. In addition, the effectiveness of the proposed algorithm is verified by comparison with some high-performing algorithms for the considered problem.     

A bi-objective model for design and analysis of sustainable intermodal transportation systems: a case study of Turkey

This paper presents a mixed-integer linear optimisation model to analyse the intermodal transportation systems in the Turkish transportation industry. The solution approach includes mathematical modelling, data analysis from real-life cases and solving the resulting mathematical programming problem to minimise total transportation cost and carbon dioxide emissions by using two different exact solution methods in order to find the optimal solutions. The novel approach of this paper generates Pareto solutions quickly and allows the decision makers to identify sustainable solutions by using a newly developed solution methodology for bi-objective mixed-integer linear problems in real-life cases.     

A Three Phased Approach To Final Exam Scheduling

A multi-phase examination scheduling process applicable to large university settings in general and SUNY at Buffalo (SUNYAB) in particular is proposed. Each scheduling phase is considered an integral part of the overall scheduling process and solved independently. Phase one of scheduling process is wth the assignment of examinations to exam blocks (each containing one or more exams). The objective of this phase is to minimize the number of students taking more than one exam in the same exam block. The problem is solved using a variation of the quadratic assignment problem. Phase two of the scheduling process uses the results from phase one as input. The exam blocks are assigned to exam days in such a way that some measure of students' comfort is maintained. Phase two of the scheduling process is formulated as a set covering problem with an extra constraint. Phase three of the scheduling process which is involved wt h the assignment of exam blocks to exam periods in each day and optimal ordering of exam days is solved heuristically using a traveling salesman problem as part of solution procedure. The performance of the algorithms devised for the multi-phase scheduling process are tested both in terms of quality of the solutions obtained and the computer time to generate these solutions.     

Minimising makespan on parallel machines with precedence constraints and machine eligibility restrictions

The block erection problem is defined as a parallel machine scheduling problem with precedence constraints and machine eligibility restrictions. A heuristic algorithm combined of the largest total amount of processing first rule (LTAP) and the enhanced smallest machine load first rule (ESML) is proposed to minimise makespan for the block erection in a shipyard. Finally, four lower bounds and the percentage of the reduced makespan compared with the current solutions are defined to evaluate the performance of the proposed algorithm. The experiments are performed on data selected from a shipbuilding company, and the results demonstrate that the presented algorithm can effectively find a good solution to minimise the makespan of the block erection problem.     

A job shop distributed scheduling based on Lagrangian relaxation to minimise total completion time

This paper considers a distributed job shop scheduling problem where autonomous sub-production systems share common machines with each other. Each sub-production system is responsible for the scheduling of a set of jobs to minimise the total completion time on shared machines. A sub-production system has ultimate responsibility on maintaining private information such as objective function, processing time and routings on shared machines. Also sub-production systems must cooperate each other in order to achieve a global goal while sharing minimum of private information. In this research, we propose a distributed cooperation method in which sub-production systems and shared machines interact with one another to find a compromised solution between a locally optimised solution and a system-wide solution. We tested the proposed method for small, medium and large size of job shop scheduling problems and compared to a global optimal solutions. The proposed method shows promising results in terms of solution qualities and computational times.     

A two-stage three-machine assembly scheduling problem with a position-based learning effect

The two-stage assembly scheduling problem has attracted increasing research attention. In many such problems, job processing times are commonly assumed to be fixed. However, this assumption does not hold in many real production situations. In fact, processing times usually decrease steadily when the same task is performed repeatedly. Therefore, in this study, we investigated a two-stage assembly position-based learning scheduling problem with two machines in the first stage and an assembly machine in the second stage. The objective was to complete all jobs as soon as possible (or to minimise the makespan, implying that the system can perform better and efficient task planning with limited resources). Because this problem is NP-hard, we derived some dominance relations and a lower bound for the branch-and-bound method for finding the optimal solution. We also propose three heuristics, three versions of the simulated annealing (SA) algorithm, and three versions of cloud theory-based simulated annealing algorithm for determining near-optimal solutions. Finally, we report the performance levels of the proposed algorithms.     

A Meta-RaPS for the early/tardy single machine scheduling problem

This paper investigates a meta-heuristic solution approach to the early/tardy single machine scheduling problem with common due date and sequence-dependent setup times. The objective of this problem is to minimise the total amount of earliness and tardiness of jobs that are assigned to a single machine. The popularity of just-in-time (JIT) and lean manufacturing scheduling approaches makes the minimisation of earliness and tardiness important and relevant. In this research the early/tardy problem is solved by Meta-RaPS (meta-heuristic for randomised priority search). Meta-RaPS is an iterative meta-heuristic which is a generic, high level strategy used to modify greedy algorithms based on the insertion of a random element. In this case a greedy heuristic, the shortest adjusted processing time, is modified by Meta-RaPS and the good solutions are improved by a local search algorithm. A comparison with the existing ETP solution procedures using well-known test problems shows Meta-RaPS produces better solutions in terms of percent difference from optimal. The results provide high quality solutions in reasonable computation time, demonstrating the effectiveness of the simple and practical framework of Meta-RaPS.     

Convex resource allocation scheduling in the no-wait flowshop with common flow allowance and learning effect

We study the problem of two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times. Under the condition of the due-date assignment with common flow allowance (i.e. slack (SLK) due-date assignment), we provide a bi-criteria analysis where the first criterion is to minimise the scheduling criteria (i.e. the weighted sum of earliness, tardiness and flow allowance costs), and the second criterion is to minimise the resource consumption cost (i.e. the weighted sum of resource consumption cost). The objective is to determine the optimal job sequence, resource allocations and common (flow allowance) slack time that minimise the three different versions of the two criteria. We prove that these problems can be solved in polynomial time.     

Single machine scheduling problem with stochastic sequence-dependent setup times

In this study, we consider stochastic single machine scheduling problem. We assume that setup times are both sequence dependent and uncertain while processing times and due dates are deterministic. In the literature, most of the studies consider the uncertainty on processing times or due dates. However, in the real-world applications (i.e. plastic moulding industry, appliance assembly, etc.), it is common to see varying setup times due to labour or setup tools availability. In order to cover this fact in machine scheduling, we set our objective as to minimise the total expected tardiness under uncertain sequence-dependent setup times. For the solution of this NP-hard problem, several heuristics and some dynamic programming algorithms have been developed. However, none of these approaches provide an exact solution for the problem. In this study, a two-stage stochastic-programming method is utilised for the optimal solution of the problem. In addition, a Genetic Algorithm approach is proposed to solve the large-size problems approximately. Finally, the results of the stochastic approach are compared with the deterministic one to demonstrate the value of the stochastic solution.     

A two-stage three-machine assembly scheduling problem with deterioration effect

The two-stage assembly scheduling problem has received growing attention in the research community. Furthermore, in many two-stage assembly scheduling problems, the job processing times are commonly assumed as a constant over time. However, it is at odds with real production situations some times. In fact, the dynamic nature of processing time may occur when machines lose their performance during their execution times. In this case, the job that is processed later consumes more time than another one processed earlier. In view of these observations, we address the two-stage assembly linear deterioration scheduling problem in which there are two machines at the first stage and an assembly machine at the second stage. The objective is to complete all jobs as soon as possible (or to minimise the makespan, implies that the system can yield a better and efficient task planning to limited resources). Given the fact that this problem is NP-hard, we then derive some dominance relations and a lower bound used in the branch-and-bound method for finding the optimal solution. We also propose three metaheuristics, including dynamic differential evolution (DDE), simulated annealing (SA) algorithm, and cloud theory-based simulated annealing (CSA) algorithm for find near-optimal solutions. The performances of the proposed algorithms are reported as well.     

Job shop scheduling with the option of jobs outsourcing

Incorporating outsourcing in scheduling is addressed by several researchers recently. However, this scope is not investigated thoroughly, particularly in the job shop environment. In this paper, a new job shop scheduling problem is studied with the option of jobs outsourcing. The problem objective is to minimise a weighted sum of makespan and total outsourcing cost. With the aim of solving this problem optimally, two solution approaches of combinatorial optimisation problems, i.e. mathematical programming and constraint programming are examined. Furthermore, two problem relaxation approaches are developed to obtain strong lower bounds for some large scale problems for which the optimality is not proven by the applied solution techniques. Using extensive numerical experiments, the performance of the solution approaches is evaluated. Moreover, the effect the objectives's weights in the objective function on the performance of the solution approaches is also investigated. It is concluded that constraint programming outperforms mathematical programming significantly in proving solution optimality, as it can solve small and medium size problems optimally. Moreover, by solving the relaxed problems, one can obtain good lower bounds for optimal solutions even in some large scale problems.     

Parallel machine scheduling problem with ready times,due times and sequence-dependent setup times using meta-heuristic algorithms

This article considers a parallel machine scheduling problem with ready times, due times and sequence-dependent setup times. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the weighted sum of setup times, delay times and tardy times. A mathematical model for optimal solution is derived. An in-depth analysis of the model shows that it is very complicated and difficult to obtain optimal solutions as the problem size becomes large. Therefore, two meta-heuristics, genetic algorithm (GA) and a new population-based evolutionary meta-heuristic called self-evolution algorithm (SEA), are proposed. The performances of the meta-heuristic algorithms are evaluated through comparison with optimal solutions using several randomly generated examples.     

Integrated multi-factory production and distribution scheduling applying vehicle routing approach

This paper introduces a new integrated multi-factory production and distribution scheduling problem in supply chain management. This supply chain consists of a number of factories joined together in a network configuration. The factories produce intermediate or finished products and supply them to other factories or to end customers that are distributed in various geographical zones. The problem consists of finding a production schedule together with a vehicle routing solution simultaneously to minimise the sum of tardiness cost and transportation cost. A mixed-integer programming model is developed to tackle the small-sized problems using CPLEX, optimally. Due to the NP-hardness, to deal with medium- and large-sized instances, this paper develops a novel Improved Imperialist Competitive Algorithm (IICA) employing a local search based on simulated annealing algorithm. Performance of the proposed IICA is compared with the optimal solution and also with four variants of population-based metaheuristics: Imperialist Competitive Algorithm, Genetic Algorithm, Particle Swarm Optimisation (PSO), and Improved PSO. Based on the computational results, it is statistically shown that quality of the IICA’s solutions is the same as optimal ones solving small problems. It also outperforms other algorithms in finding near-optimal solutions dealing with medium and large instances in a reasonably short running time.     

A greedy algorithm to determine the number of transporters in a cyclic electroplating process

This paper presents a local optimization algorithm for minimizing the number of transporters required for material handling in a cyclic processing line. Within a cycle, a given set of transportation operations must be performed. Each operation consists of picking up a work-in-process job at a stage and delivering it to the next stage. The length of time that a job can remain at a particular stage is restricted by a time window. The transporters that perform the operations move on a shared track, and traffic collisions must be avoided during their movements. To avoid traffic collisions, the operations are partitioned into groups, where each group is served by a single transporter. A local optimal solution is obtained when the group sizes are maximized. We show that the duals of the linear programming subproblems formulated in the process of maximizing the group sizes are specially structured shortest-path problems. This leads to an effective search method for the maximization problem. Conditions when die proposed algorithm achieves die global optimal solution are discussed. The algorithm's performance is evaluated on both randomly generated test problems and benchmark problems.     

Modelling and scheduling analysis of multi-cluster tools with residency constraints based on time constraint sets

This paper is dedicated to the scheduling problem of multi-cluster tools with process module residency constraints and multiple wafer product types. The problem is formulated as a non-linear programming model based on a set of time constraint sets. An effective algorithm called the time constraint sets based (TCSB) algorithm is presented as a new method to schedule the transport modules to minimise the makespan of a number of wafers. In approach, time constraint sets are maintained for all the resources and necessary operations to exploit the remaining production capacities during the scheduling process. To validate the proposed algorithm on a broader basis, a series of simulation experiments are designed to compare our TCSB algorithm with the benchmark with regard to cluster factor, configuration flexibilities and the variation of the processing times and residency constraint times. The results indicate that the proposed TCSB algorithm gives optimal or near optimal scheduling solutions in most cases.     

Unrelated parallel machine scheduling with setup times and ready times

We consider the problem of scheduling unrelated parallel machines with sequence- and machine-dependent setup times and ready times to minimise total weighted tardiness (TWT). We present a mixed integer programming model that can find optimal solutions for the studied problem. We also propose a heuristic (ATCSR_Rm) and an iterated hybrid metaheuristic (IHM) that can find optimal or nearly optimal solutions for the studied problem within a reasonable time. The proposed IHM begins with effective initial solutions, and then improves the initial solutions iteratively. The IHM integrates the principles of the attraction–repulsion mechanism within electromagnetism-like algorithms with local search. If the search becomes trapped at a local optimum, an elite search procedure is developed to help the search escape. We have compared our proposed IHM with two existing metaheuristics, tabu search (TS) and ant colony optimisation (ACO). Computational results show that the proposed IHM outperforms TS and ACO in terms of TWT for problem instances of all sizes.     

Production scheduling of single-stage multi-product batch chemical processes with fixed batch sizes

We address the problem of scheduling a single-stage multi-product batch chemical process with fixed batch sizes. We present a mixed-integer nonlinear programming model to determine the schedule of batches, the batch size, and the number of overtime shifts that satisfy the demand at minimum cost for this process. We introduce a polynomial-time algorithm to solve the problem when the processing times of all batches are identical and the setup and cleaning times are sequence-independent. The solution procedure is based on recognizing that the optimal fixed batch size is a member of a set whose cardinality is polynomial. Given a batch size, the problem may be formulated as an assignment problem. Thus, an optimal solution may be found by iteratively solving a polynomial number of assignment problems. This work was motivated by a pesticide manufacturing company in the design of a new plant where the assumptions of a single bottleneck machine, fixed batch sizes, sequence-independent setup times, and identical batch processing times are all valid. An example is developed for this application.