Optimisation approaches for distributed scheduling problems

Distributed scheduling problems are challenging tasks to researchers and practitioners that have been gaining increasing popularity in recent years. This is partly attributed to the fact that multi-site production and supply chain integration are not uncommon nowadays as a consequence of globalisation. Companies have established new production sites in different locations or formed strategic partnerships with their supply chain members in order to increase their responsiveness to market changes and to share resources more efficiently among themselves through the integrated production systems. Co-operation among different sites becomes more critical. Thus, development of an effective and efficient optimisation approach for concurrent planning and scheduling to maximise the overall benefits subject to such settings have become even more challenging to researchers. This special issue aims at gathering the state-of-the-art research in this area.

1 Trends of Distributed Scheduling

The upheaval effect of globalisation on production systems has made them become more flexible, reconfigurable, open, and demand-driven. Traditional centralised scheduling approaches where all manufacturing activities and resources are controlled by single decision maker are no longer as useful as in the past. This is owing to the fact that they are less responsive to emergencies, inflexible, and unable to satisfy the unexpected dynamic market needs (Lou, Ong, and Nee 2010). To enhance responsiveness to changes and international competitiveness under the trend of globalisation, many enterprises therefore started to shift from traditional single-site production to multi-site production through establishment of new sites, merging, and acquisitions (Lau et al. 2006). These sites are not necessarily located close to each other, but may be geographically distributed in various locations and even in different countries. In so doing, enterprises can thus take the advantages of being closer to customers, complying with local laws, specialising on product types, effective products marketing, and being able to quickly respond to market changes (Schniederjans 1999; Sule 2001).

In multi-sites network, each site is responsible for performing a range of tasks that may be unique in that particular site. They may be subjected to various constraints, such as labour cost and skills, process technology, local suppliers, transportation facilities, government policy, and country taxation system. As a consequence, different sites would have different production lead times, operating costs, efficiencies, and customer service levels. All these lead to a growing concern on distributed scheduling problems (Timpe and Kallrath 2000), and have become a popular topic among researchers and industrialists.

2 Purpose of distributed scheduling

The aim of distributed scheduling is to enhance system reliability and utilisation of resources through effective allocation of processes and collaboration between jobs in a supply chain. A distributed system can be regarded as a range of processes that need to be performed in various locations (nodes), subject to numerous constraints, such as capacity, time, and tooling (Wang 2003; Cicirello 2004). In distributed scheduling, all available resources are shared among entities and thus collaboration between entities can never be ignored.

Compared with traditional scheduling problems in a single site, distributed scheduling problems are a lot more complicated in nature and are classified as NP-hard problems (Garey and Johnson 1979). One major task of a distributed scheduling problem includes determining a schedule that can meet all timing and logical constraints of the planned activities. It mainly consists of two issues. First, to assign various jobs to suitable nodes and, second, to establish the production schedules in each node (Cohen and Lee 1998; Barroso, Leite, and Loques 2002). Whenever an activity is being assigned to a site for processing, it becomes uneconomical and difficult to transfer the semi-finished part to other sites for the remaining operations. As distributed scheduling relies on the results on job allocation, performances such as makespan, total operating cost, and order fulfilment, would be different from site to site. The complexity of the scheduling problem therefore greatly increases (Chan et al. 2006b).

3 Existing work on distributed scheduling

Distributed scheduling is an optimisation process where limited production resources are assigned between parallel and sequential activities over time. It can be viewed as one of the scheduling problems that encounter the greatest difficulty, especially when it happens in an open environment (Zweben and Fox 1994). Owing to its dynamic nature, combinatorial aspects, and its practical interest, the distributed scheduling problem has gained substantial attentions in the literature. The proposed solutions from many different researchers can mainly be divided into two categories, namely the heuristic-based approaches and the agent-based approaches (Lou, Ong, and Nee 2010).

3.1 Heuristic-based approach

Distributed scheduling problems are regarded as NP-hard in many cases. As a result, using heuristic methodologies to attain a near optimal solution in a reasonably shorter period is more realistic than using traditional analytical approaches. These heuristic approaches include genetic algorithms, simulated annealing, tabu search, constraint satisfaction and optimisation, and neural networks, and so on.

For instance, DiNatale and Stankovic (1995) considered distributed static systems with simulated annealing algorithm where jobs are sporadic and have random precedence, deadlines, and exclusion constraints. Jia et al. (2002) focused on distributed manufacturing environment and proposed a multi-functional scheduling system through the use of neural networks. Sakawa (2002) integrated fuzzy logic and genetic algorithms to model uncertainties of order due date and production lead time in distributed scheduling problems. Chan, Chung, and Chan (2006a) introduced a new encoding mechanism using genetic algorithms approach to enhance reliability of the optimisation results. Chung, Chan, and Chan (2009) proposed a modified genetic algorithm approach with maintenance considerations being added for distributed scheduling. More heuristic approaches can be found in Santos et al. (1997), Mori and Tseng (1997), Jawahar, Aravindan, and Ponnambalam (1998), Ghedjati (1999), Satake et al. (1999), Beck and Fox (2000), Barroso, Leite, and Loques (2002), Chan, Chung, and Chan (2005), and Naderi and Ruiz (2010).

3.2 Agent-based approach

Apart from the heuristic methods, multi-agent systems technology has also been considered as another promising approach in solving distributed scheduling problems in dynamic manufacturing environments (Lou, Ong, and Nee 2010; Chan and Chan 2010). Every job schedule and negotiation mechanism is handled by a single agent among other agents to execute distributed scheduling in an agent-based manufacturing scheduling system. In other words, seach agent is required to handle and monitor its own schedule. Through negotiation and co-ordination between all agents, a global scheduling can then be determined (Chan and Chan 2004). The agent-based approach is able to benefit manufacturing scheduling in various ways (Shen, Maturana, and Norrie 2000). For instance, it offers greater flexibility and more reactive agents, which could lead to a more scalable and robust global schedule. This technique is then being regarded as a promising paradigm for distributed manufacturing systems in the next generation (Shen et al. 2006; Chan and Chan 2009).

In general, two major types of scheduling systems can be distinguished with respect to the two approaches for agent decomposition: functional and physical decomposition (Shen 2002). In functional decomposition agent systems, each agent represents a single resource involved in the system (e.g. machine, material, man power, etc.) and is responsible for keeping in track the schedule of this resource. By active negotiation between agents, scheduling is made possible and a global schedule would be the final product. In physical decomposition agent systems, scheduling is carried out through incremental searching processes. The major duty of agents in scheduling is to carry out local incremental search. After merging all local schedules and backtracking, the global schedule could be obtained (Sycara et al. 1991).

Numerous researches have been carried out in performing distributed scheduling with agent-based systems collaborated in the recent decade. Peng and Mcfarlane (2004) introduced a multi-agent based independent and distributed approach to facilitate manufacturing systems in adapting to changing circumstances in the aspects of both variation in products and upgrades in production system. Azevedo et al. (2004) addressed the constraints of a made-to-order environment, and formulated multi-agent system architecture for distributed manufacturing firms to deal with concurrent customer-order planning. Walker, Brennan, and Norrie (2005) created a dynamic and responsive scheduler through integration of the traditional heuristic job-shop scheduling approaches with artificial intelligence techniques. The scheduler was executed as a multi-agent system with a holonic manufacturing system architecture implemented. Rodriguez-Moreno et al. (2006) extended the reasoning capabilities of classical planners and presented hybrid integration, namely integrated planning and scheduling system (IPSS), to perform constraint-based reasoning. Lau et al. (2006) introduced an agent-based distributed scheduling model to support scheduling among multiple independent enterprises based on modified contract-net protocol within a supply chain.

Table 1 shows a brief summary of examples of past literature on distributed manufacturing scheduling problems solved by different methods.

Table 1. Summary of past literature on distributed manufacturing scheduling.

Methods	Authors	Focuses
Genetic algorithm (GA)	Mori and Tseng (1997)	Scheduling with multi-mode resources constraints
	Jawahar, Aravindan, and Ponnambalam (1998)	Derivation of optimal combination of priority dispatching rules
	Ghedjati (1999)	Job-shop scheduling with unrelated parallel machines and precedence constraints with minimisation of completion time
	Chan et al. (2005)	Improvements of gene search performance by determining optimised crossover rate
	Chan, Chung, and Chan (2006a)	Optimisation reliability enhancement
	Chung, Chan, and Chan (2009)	Scheduling with considerations of machine maintenance added
Fuzzy logic	Shaout (1998)	Load balancing of individual processor and throughput optimisation of overall system
	Sakawa (2002)	Uncertainties of order due dates and production lead time
	Satake et al. (1999)	Job-shop scheduling with minimisation of makespan
Simulated annealing	Low (2005)	Multi-stage flow-shop scheduling with minimisation of total system flow time
	Chan et al. (2013)	Consideration of transportation time between factories with minimisation of makespan
	Barroso, Leite, and Loques (2002)	Development of utility functions with minimisation of service time of tasks
Bayesian algorithm	Naderi and Ruiz (2010)	Permutation flow-shop scheduling with minimisation of maximum completion time and makespan
Mixed integer linear programming	Beck and Fox (2000)	Scheduling with optimisation of alternative resources and process plan
Constraint satisfaction	Azevedo et al. (2004)	Real time scheduling under make-to-order environment with considerations of concurrent customer-orders planning
Multi-agent based	Peng and Mcfarlane (2004)	Flow-shop scheduling with changing circumstance such as product variation and system upgrades
	Walker, Brennan, and Norrie (2005)	Dynamic and responsive job-shop scheduling system based on evolutionary algorithms
	Rodriguez-Moreno et al. (2006)	Management of precedence constraints, temporal requirements and multi-capacity resource consumption
	Lau et al. (2006)	Scheduling among independent enterprises with considerations of delay, quality and cost, and evaluation of partners based on contract-net protocol

4 Scanning the issue

Globalisation and market unpredictability has led many companies to enlarge their production and distribution network. The existence of decentralised production and distribution sites requires co-operation and optimisation in the use of shared resources, in particular, in the definition of inventory levels to deal with market demand uncertainty. Fernandes, Gouveia, and Pinho (2013) intend to calculate the most appropriated overstock level and to measure the impact of demand uncertainty at each network decision point. By investigating both market uncertainty and management flexibility in a sequential decision process, they have adapted the real options methodology to calculate the optimal overstock value and analyse the uncertainty impact, in a model characterised by a dynamic design in manufacturing and distribution stocking points. The results describe the relationship between the inventory level and the market demand uncertainty impact through the network; they also show that the distortions in information integration, or lack of global co-ordination, can have a huge impact on the inventory levels, which supports that inventory management and production scheduling must be integrated and balanced at different decision points under an optimisation approach.

Motivated by many real-world industrial practices, Yeung, Choi, and Cheng (2013) study a multiple-supplier, single-warehouse operator, single-manufacturer, and two-machine supply chain scheduling problem. The problem is known to be a challenging distributed scheduling problem. To be specific, they consider both the optimal scheduling and supply chain co-ordination issues under two supply chain scenarios, namely decentralised and centralised supply chains. In the decentralised supply chain, they explore the case when the profit function depends on the storage time, storage quantity, order sequence-dependent weighted storage costs, and idle time of the orders. For the centralised supply chain, they assume that a supply chain co-ordinator exists who aims at selecting the orders, maximising the profit of the whole supply chain, and co-ordinating the supply chain members to share the optimal supply chain profit. They formulate both scenarios as the two-machine flow shop scheduling optimisation problems with common due windows. They develop a theorem and two algorithms to solve these problems. They also propose a novel profit sharing contract which can achieve supply chain co-ordination.

Research in multi-site scheduling problems is very important nowadays due to the global manufacturing arena. Distributed scheduling is an important and complex problem as it is the allocation of jobs to various machines as well as factories which are geographically distributed. To solve such a complex problem Chan et al. (2013) propose a hybrid algorithm, which includes both tabu and sample sort simulated annealing. This algorithm overcomes the negative aspects of both algorithms. The main objective is to minimise the make-span, which includes the processing time, waiting time, and transportation time from one factory to another factory. In this connection, it is a more complex problem than classical scheduling problem as it considers both factories and machines inside the factories.

It is always a challenge to achieve operational efficiency in a manufacturing facility; not to mention when considering multi-site facilities that possess even greater complexity and have a wider range of constraints and variables to take into account, such as related to production capability/efficiency, transportation facility, communication means, inventory control, storage space, workforce rate and skill level, government policy and tax, and possibly time zone and working culture. Lim and Tan (2013) in their paper introduce the use of a multi-agent system to achieve this operational efficiency through optimising resource utilisation within multi-site production facilities. The agent system consists of a collection of autonomous and intelligent agents to integrate process planning and production scheduling activities across these facilities, so as to ensure an optimised solution can be generated to best use of the facilities available within an organisation.

Zhou et al. (2013) study the benefit of original equipment manufacturers (OEM) from the decentralised control mode under which they ignore the internal cannibalisation rather than the re-manufacturing option. They consider a decentralised closed-loop supply chain in which one OEM can purchase new components from one supplier to produce new products and collect used products from consumers to produce re-manufactured products. They reveal that the decentralised control within the OEM can outperform the centralised control when the cost structure of producing new and re-manufactured products satisfies certain conditions.

Distributed scheduling is a complicated problem of manufacturing and supply network as the process interacts with one another. To have high efficiency in distributed manufacturing system, enterprise needs to manage the potential risks and assess the impact of those risks in the production schedule so as to ensure products with good quality can be produced and shipped on time. Lee, Lv, and Hong (2013) in their paper adopted Petri Net to model the production system and the inter-relationship of the production process in concurrent, discrete-event dynamic system can be analysed. Researchers in this study simulate the potential quality risk happening in production with Monte Carlo simulation and the impact on lead time and quality cost are evaluated through simulation of different scenarios. This paper contributes a qualitative approach for analysing the potential impact and occurrence probability of the risk so as to justify the necessity of scenario planning in distributed scheduling. The case example is given to illustrate the detailed components in the proposed workflow and to help show the feasibility of application in an industrial environment.

Distributed scheduling problems usually attempt to achieve only its local objective without considering the global objective and a contradictory problem might occur between the local objective and the overall system performance. Wang, Cheng, and Lin (2013) discuss the challenges of a decentralised manufacturing system such as how to achieve global optimisation in decentralisation systems, how to specify the dynamic behaviour of autonomous agents, and how to embrace learning and self-adaptive capabilities, etc. They develop a distributed scheduling algorithm called closed-loop feedback simulation (CLFS) approach which includes adaptive control of the auction-based bidding sequence to prevent the first bid first serve rule and may dynamically allocate production resources to operations. Therefore, the result shows that iterative adjustment of bidding sequence can reduce the due date deviation with completion time in the distributed scheduling problem.

One specific supply chain co-ordination problem that has not received proper attention in the literature so far is concerned with the changes of one process in the case of its planning or modernisation. Ivanov et al. (2013) coin the phrase ‘process modernisation’. An example of process modernisation is the replacement of old machines with more productive ones with the aim of attracting new customer orders. This replacement is to be performed so that, on one hand, the service level for existing customers is not decreased and, on the other hand, the introduction of new machines does not affect process execution by suppliers and their own production plants. This problem is basically different from the existing studies due to the presence of the so-called transition (change) period of time. During this period, three processes (the modernisation, the process under modernisation, and the interlinked process) should be performed jointly, unlike in maintenance scheduling where the machines are stopped during the maintenance. In this study, a new dynamic model for co-ordinated scheduling of interlinked processes in a supply chain during the process of modernisation is presented. The considered problem is represented as a special case of the scheduling problem with dynamically distributed jobs. The supply chain is modelled as a networked controlled system described through a dynamic interpretation of the operations’ execution. The peculiarity of the proposed approach is the dynamic interpretation of scheduling based on a natural dynamic decomposition of the problem and its solution with the help of a modified form of continuous maximum principle blended with combinatorial optimisation.

Li, Zhou, and Wang (2013) investigate the problem of channel choice in two power-imbalanced supply chains, consisting of the leader supply chain and the follower supply chain. They assume that there exists symmetric and asymmetric cost information between the two supply chains, and that the two chains as well as two members in each chain follow the Stackelberg game setting. They investigate the impact of power imbalance, information asymmetries, and the degree of product substitutability on the equilibrium channel structure and the supply chain players’ performances. The analysis provides guidance to firms in considering the channel structure for the design. They also analyse which and when a particular distribution channel structure outperforms the other and what an equilibrium distribution channel structure is. In addition, they focus on how the channel structure strategies depend on the power imbalance, information asymmetries, and the degree of product substitutability.

Supply chain planning approaches can be classified into two main planning systems: centralised and decentralised planning approaches. The centralised approach can theoretically optimise supply chain performance, although its implementation requires a high degree of information exchange among supply chain partners. This leads to difficulties when independent partners do not want to share information. In order to address these difficulties, decentralised approaches are designed for supply chains where each member is a separate economic entity that makes its operational decisions independently, yet with some minimal level of information sharing. Taghipour and Frayret (2013) focus on co-ordination of two partners of supply chain linked by material and non-strategic information flows by a dynamic mutual adjustment search heuristic. Their work considers the fact of changing the production environment from traditional single-site production to decentralised multi-site production network and the important role of co-ordination among different sites. They propose an effective and efficient decentralised optimisation for co-ordination of two partners of a supply chain. This co-ordination approach, entitled ‘dynamic mutual adjustment search’, tries to produce near to optimal solutions for all partners of a supply chain.

Thomas et al. (2013) consider a planning and scheduling problem motivated by the coal supply chains in Australia. In this problem there are several independent decision makers who plan and schedule resources based on capacities that are generally known and demands that are only known to the resource owners. They present a mixed integer programming formulation which minimises total weighted earliness, tardiness and operational costs. They also present a distributed algorithm based on Lagrangian relaxation, which incorporates concepts from the Volume algorithm and Wedelin algorithm. The strength of the distributed algorithm is demonstrated by extensive computational experiments on several randomly generated instances. The paper highlights effectiveness of the Lagrangian relaxation approach by distributing the decisions to the decision-making units. The approach has significant advantageous over other traditional sequential or integrated modelling approaches. Another key contribution of the paper is in methodologies for fine tuning of the Lagrangian relaxation algorithm. Heuristics that provide tight bounds for such problems are also presented.

Hammami and Frien (2013) present a mixed integer programming model for the design of global multi-echelon supply chains while considering lead time constraints. They consider the delivery lead time of purchasing, manufacturing and transportation that are triggered by the customer order while considering the stock levels of purchased, intermediate and final products that must be kept at the different facilities.

Ogier et al. (2013) study a two-echelon supply chain with one manufacturer and multiple independent retailers with Quantity Discount contract. The problem consists of planning productions, transportations and storage activities in supply chain at tactical level on a finite horizon. The main features considered are decentralised decision making and iteration of the planning process on a rolling horizon basis. They propose multi-agent approach to model the supply chain behaviour.

Conclusion

The significance of a distributed system has been highly recognised by researchers and industrialists in the recent decade due to the changes in today’s manufacturing environment. Traditional single site production has eventually been shifted to multi-site under the trend of globalisation. To enhance competitiveness and resources utilisation in the current market environment, distributed scheduling has therefore become more essential for enterprises to create efficient and effective production schedules for geographically separated manufacturing plants.

Acknowledgements

First and foremost, the guest editors are grateful to all anonymous reviewers for their valuable effort in reviewing the papers submitted to this special issue. They have helped to maintain the quality of the papers published in this special issue. Their timely feedback also helped the guest editors meet the publication schedule. In addition, we would like to thank all the authors for their contributions.

Last but not least, we would like to take this opportunity to thank John Middle and Professor Alexandre Dolgui, former and current Editor-in-Chief of the International Journal of Production Research respectively, for publishing this special issue. We would also like to express our gratitude to the editorial and publishing team who provided all necessary support to us. Finally, the guest editors hope you will enjoy reading the special issue as much as we have enjoyed editing it.