摘要 :
Since the Third Industrial Revolution, technology and the global economy have developed rapidly. Driven by market demand and the development of science and technology, the organisational model of the production system has evolved,...
展开
Since the Third Industrial Revolution, technology and the global economy have developed rapidly. Driven by market demand and the development of science and technology, the organisational model of the production system has evolved, which has in turn caused changes in the methods of production scheduling. In the context of the newest industrial revolution (Industry 4.0), this review aims to examine the evolution of production scheduling in terms of economics and technology. First, literature on production scheduling is summarised and analysed from the perspectives of centralised/decentralised scheduling, distributed scheduling, and cloud manufacturing scheduling. Second, future challenges and trends in the development of production scheduling are discussed in view of the globalisation of manufacturing and changes in production modes enabled by new technologies. Finally, based on the findings of this review, we make a prediction for the future expansions of the customer-centric value chain as well as changes in product design and production methods brought by product personalisation.
收起
摘要 :
Reactive schedule repair is a better alternative to total rescheduling of impaired job shop schedules. For ease of implementation in the job shops, heuristic-based schedule repair methods are preferred. However, the majority of th...
展开
Reactive schedule repair is a better alternative to total rescheduling of impaired job shop schedules. For ease of implementation in the job shops, heuristic-based schedule repair methods are preferred. However, the majority of the repair heuristics reported in the literature are capable of handling only a singular disruption to the schedule. On the contrary, real-world job shops are subjected to multiple complex disruptions that occur randomly over the span of the schedule. A new heuristic, modified affected operation rescheduling (mAOR), has been successfully used for repairing a majority of typical job shop disruptions such as absenteeism of workers, process time variations and arrival of unexpected jobs using a combination of generic repair steps. In the present work, the mAOR heuristic has been applied for repairing randomly occurring multiple disruptions under rigorous shop floor conditions. The relationship between the variation of shop floor conditions and the performance of the schedule repair heuristic is investigated to substantiate the effectiveness of the mAOR heuristic. The results of extensive experimentation indicate that the performance of the mAOR heuristic is superior to the right shift rescheduling heuristic (a commonly cited repair heuristic).
收起
摘要 :
This paper introduces a general methodology to perform a comparative evaluation of different approaches to the problem of scheduling with uncertainty. Different proactive (off-line) and reactive (on-line) scheduling policies are e...
展开
This paper introduces a general methodology to perform a comparative evaluation of different approaches to the problem of scheduling with uncertainty. Different proactive (off-line) and reactive (on-line) scheduling policies are evaluated by simulating the execution of a number of baseline schedules under uncertain environmental conditions, and observing the solution behaviors as such schedules get stressed by exogenous events. The analysis aims at assessing the impact of both proactive and reactive scheduling efforts on the robustness of the baseline solutions, against measurable disrupting factors, through reproducible experiments. As the results show, this dynamic approach reveals extremely useful to unveil some subtle aspects, which would have remained undetected through static metric evaluations.
收起
摘要 :
This paper introduces a general methodology to perform a comparative evaluation of different approaches to the problem of scheduling with uncertainty. Different proactive (off-line) and reactive (on-line) scheduling policies are e...
展开
This paper introduces a general methodology to perform a comparative evaluation of different approaches to the problem of scheduling with uncertainty. Different proactive (off-line) and reactive (on-line) scheduling policies are evaluated by simulating the execution of a number of baseline schedules under uncertain environmental conditions, and observing the solution behaviors as such schedules get stressed by exogenous events. The analysis aims at assessing the impact of both proactive and reactive scheduling efforts on the robustness of the baseline solutions, against measurable disrupting factors, through reproducible experiments. As the results show, this dynamic approach reveals extremely useful to unveil some subtle aspects, which would have remained undetected through static metric evaluations. Keywords Scheduling with uncertainty - Reactive scheduling - Proactive scheduling - Schedule execution
收起
摘要 :
In this paper we introduce the Personnel Task Scheduling Problem (PTSP) and provide solution algorithms for a variant of this problem known as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). The PTSP is a proble...
展开
In this paper we introduce the Personnel Task Scheduling Problem (PTSP) and provide solution algorithms for a variant of this problem known as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). The PTSP is a problem in which a set of tasks with fixed start and finish times have to be allocated to a heterogenous workforce. Personnel work in shifts with fixed start and end times and have skills that enable them to perform some, but not all tasks. In other words, some personnel are qualified to only perform a subset of all tasks. The objective is to minimise the overall cost of personnel required to perform the given set of tasks. In this paper we introduce a special case in which the only cost incurred is due to the number of personnel (shifts) that are used. This variant of the PTSP is referred to as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). While our motivation is a real-life Personnel Task Scheduling Problem, the formulation may also be applied to machine shop scheduling. We review the existing literature, provide mathematical formulations, and develop a heuristic approach for the SMPTSP.
收起
摘要 :
Parallelization paradigms for effective execution in a Directed Acyclic Graph (DAG) application have been widely studied in the area of task scheduling. Schedule length can be varied depending on task assignment policies, scheduli...
展开
Parallelization paradigms for effective execution in a Directed Acyclic Graph (DAG) application have been widely studied in the area of task scheduling. Schedule length can be varied depending on task assignment policies, scheduling policies, and heterogeneity in terms of each processor and each communication bandwidth in a heterogeneous system. One disadvantage of existing task scheduling algorithms is that the schedule length cannot be reduced for a data intensive application. In this paper, we propose a clustering-based task scheduling algorithm called Clustering for Minimizing the Worst Schedule Length (CMWSL) to minimize the schedule length in a large number of heterogeneous processors. First, the proposed method derives the lower bound of the total execution time for each processor by taking both the system and application characteristics into account. As a result, the number of processors used for actual execution is regulated to minimize the Worst Schedule Length (WSL). Then, the actual task assignment and task clustering are performed to minimize the schedule length until the total execution time in a task cluster exceeds the lower bound. Experimental results indicate that CMWSL outperforms both existing list-based and clustering-based task scheduling algorithms in terms of the schedule length and efficiency, especially in data-intensive applications.
收起
摘要 :
Reducing latency in distributed computing and data storage systems is gaining increasing importance. Several empirical works have reported on the efficacy of scheduling redundant requests in such systems. That is, one may reduce j...
展开
Reducing latency in distributed computing and data storage systems is gaining increasing importance. Several empirical works have reported on the efficacy of scheduling redundant requests in such systems. That is, one may reduce job latency by: 1) scheduling the same job at more than one server and 2) waiting only until the fastest of them responds. Several theoretical models have been proposed to explain the power of using redundant requests, and all of the existing results rely heavily on a common assumption: all redundant requests of a job can be immediately cancelled as soon as one of them is completed. We study how one should schedule redundant requests when such assumption does not hold. This is of great importance in practice, since cancellation of running jobs typically incurs non-negligible delays. In order to bridge the gap between the existing models and practice, we propose a new queueing model that captures such cancellation delays. We then find how one can schedule redundant requests to achieve the optimal average job latency under the new model. Our results show that even with a small cancellation overhead, the actual optimal scheduling policy differs significantly from the optimal scheduling policy when the overhead is zero. Furthermore, we study optimal dynamic scheduling policies, which appropriately schedule redundant requests based on the number of jobs in the system. Our analysis reveals that for the two-server case, the optimal dynamic scheduler can achieve 7%–16% lower average job latency, compared with the optimal static scheduler.
收起
摘要 :
In the recent past, a great deal of time and effort has been devoted to the development of job shop schedules. These schedules are able to cope with the dynamic and stochastic nature of job shops that consist of the uncertainties ...
展开
In the recent past, a great deal of time and effort has been devoted to the development of job shop schedules. These schedules are able to cope with the dynamic and stochastic nature of job shops that consist of the uncertainties both at the planning stages and on on-line execution. Deviations from predictive schedules occur when the job shop experiences both external disturbances (e.g. urgent job arrivals) and internal disruptions (e.g. machine breakdowns). To avoid complete rescheduling of the job shop a repair and recovery strategy for the schedule becomes essential. This paper provides a comprehensive review of the literature on the reactive recovery of job shop schedules and proposes further research work in this area.
收起
摘要 :
This paper is concerned with scheduling in flexible manufacturing systems (FMSs) using a fuzzy logic (FL) approach. Four fuzzy input variables: machine allocated processing time, machine priority, due date priority and setup time ...
展开
This paper is concerned with scheduling in flexible manufacturing systems (FMSs) using a fuzzy logic (FL) approach. Four fuzzy input variables: machine allocated processing time, machine priority, due date priority and setup time priority are defined. The job priority is the output fuzzy variable, showing the priority status of a job to be selected for next operation on a machine. The model will first select the machines and then assign operations based on a multi-criteria scheduling scheme. The performance of the approach is compared against established methods reported in the literature. The performance measures considered average machine utilisation, meeting due dates, setup times, work in process and mean flow times. The test results demonstrate the superiority of the fuzzy logic approach in most performance measures.
收起
摘要 :
We consider in this paper a set of generic tasks constrained by a set of uniform precedence constraints corresponding to a natural generalization of the basic cyclic scheduling problem. The two parameters of any uniform constraint...
展开
We consider in this paper a set of generic tasks constrained by a set of uniform precedence constraints corresponding to a natural generalization of the basic cyclic scheduling problem. The two parameters of any uniform constraint (namely the value and the height) between two tasks may be negative, which allows one to tackle a larger class of practical applications. We firstly study the structure and the existence of a periodic schedule. A necessary and sufficient condition for the existence of a schedule is then deduced. As there are no resource constraints, tasks following the earliest schedule have minimum average cycle times. The permanent state of the earliest schedule is characterized and we point out that the minimum average cycle times of tasks are equal for the earliest schedule and an optimal periodic schedule. An algorithm to check the existence of a schedule and to compute these minimum average cycle times using linear programming is lastly presented.
收起