Development of a new dioid algebraic model for manufacturing with the scheduling decision making capability

The dioid algebraic model, which is developed in this paper, captures the discontinuous nature of Discrete-Event Dynamic Systems and has widespread applicational capabilities. As a further improvement over existing dioid algebraic models, decision making capability is introduced to the developed dioid algebraic model. With this new capability, sequencing decisions at each machine can be represented in the model. Furthermore, the developed algebraic model is capable of representing job and resource unavailability, technological constraints, alternative process plans, and is easily modifiable to include new jobs and exclude finished jobs. In a possible application, the model can be used in representing dynamic scheduling problems and can be used as an important part of a real-time control and scheduling scheme of a manufacturing system.     

Hybrid genetic algorithm and augmented neural network application for solving the online advertisement scheduling problem with contextual targeting

Worldwide growth of the online community continues to push the popularity of internet marketing. Fueled by this trend, the online advertising industry is experiencing unprecedented revenue growth. One of the most important drivers of this revenue is banner advertising, which has long been a staple of the online advertising industry. Previous research has introduced quantitative models and solution approaches for the challenging basic scheduling optimization problem. We extend this work by incorporating the most common and popular trend in the in the industry, online advertisement targeting. In addition, motivated by the NP-hard nature of the resulting problem, we propose and test several heuristic and metaheuristic based solution techniques for the proposed problem.     

Intelligent scheduling in the manufacturing environment

This article is intended to present a model for intelligent scheduling in the manufacturing environment. The model combines an object oriented scheduler with a visual event recognizer to create an interactive visual-event intelligent scheduling tool.     

Integrating scheduling and control functions in computer integrated manufacturing using artificial intelligence

Proper integration of scheduling and control in Flexible Manufacturing Systems will make available the required level of decision-making capacity to provide a flexibly-automated, efficient, and quality manufacturing process. To achieve this level of integration, the developments in computer technology and sophisticated techniques of artificial intelligence (AI) should be applied to such FMS functions as scheduling. In this paper, we present an Intelligent Scheduling System for FMS under development that makes use of the integration of two AI technologies. These two AI technologies — Neural Networks and Expert Systems — provide the intelligence that the scheduling function requires in order to generate goodschedules within the restrictions imposed by real-time problems. Because the system has the ability to plan ahead and learn, it has a higher probability of success than conventional approaches. The adaptive behavior that will be achieved contribute to the integration of scheduling and control in FMS.     

A simulation-based scheduling system for real-time optimization and decision making support

This paper presents an industrial application of simulation-based optimization (SBO) in the scheduling and real-time rescheduling of a complex machining line in an automotive manufacturer in Sweden. Apart from generating schedules that are robust and adaptive, the scheduler must be able to carry out rescheduling in real time in order to cope with the system uncertainty effectively. A real-time scheduling system is therefore needed to support not only the work of the production planner but also the operators on the shop floor by re-generating feasible schedules when required. This paper describes such a real-time scheduling system, which is in essence a SBO system integrated with the shop floor database system. The scheduling system, called OPTIMISE scheduling system (OSS), uses real-time data from the production line and sends back expert suggestions directly to the operators through Personal Digital Assistants (PDAs). The user interface helps in generating new schedules and enables the users to easily monitor the production progress through visualization of production status and allows them to forecast and display target performance measures. Initial results from this industrial application have shown that such a novel scheduling system can help both in improving the line throughput efficiently and simultaneously supporting real-time decision making.     

Application of a continuous supervisory fuzzy control on a discrete scheduling of manufacturing systems

This paper considers the design and the practical implementation of a stable multiple objective real-time scheduling problem for a complex production system. In this paper, a complex production system is viewed as a kind of systems producing a variety of products (multiple-part-type) under constraints and multiple production objectives often conflicting. Previously, fuzzy control theory and fuzzy intervals arithmetic have been used to develop a distributed and supervised continuous-flow control architecture. In this framework, the objective of the distributed control structure is to balance the production process by adjusting the continuous production rates of the machines on the basis of the average local behavior. The supervisory control methodology aims at maintaining the overall performances within acceptable limits. In the new proposed approach, the problem of a stable real-time scheduling of jobs is considered at the shop-floor level. In this context, as the stability of the control structure is ensured, the actual dispatching times are determined from the continuous production rates through a discretization procedure. To deal with conflicts between jobs at a shared machine, a decision is made. It concerns the actual part to be processed and uses some criterions representing a measure of the job's priority. The simulation results show the validity of the proposed approach in terms of production cost, robustness and system stability.     

A distributed scheduling and shop floor control method

We suggest a market-like framework for scheduling and shop floor control in computer-controlled manufacturing systems where each resource agent and part agent acts like an independent profit maker. A part-resource negotiation procedure is suggested including price-based bid construction and price revising mechanism. Alternative routings for each production order are considered in scheduling and shop floor control. A simulation-based scheduling method is suggested to estimate the start time and the completion time of each task. We develop a prototype soffivare which utilizes the object-oriented concept.     

Computational performances of a simple interchange heuristic for a scheduling problem with an availability constraint

This paper deals with a scheduling problem on a single machine with an availability constraint. The problem is known to be NP-complete and admits several approximation algorithms. In this paper we study the approximation scheme described in He et al. [Y. He, W. Zhong, H. Gu, Improved algorithms for two single machine scheduling problems, Theoretical Computer Science 363 (2006) 257–265]. We provide the computation of an improved relative error of this heuristic, as well as a proof that this new bound is tight. We also present some computational experiments to test this heuristic on random instances. These experiments include an implementation of the fully-polynomial time approximation scheme given in Kacem and Ridha Mahjoub [I. Kacem, A. Ridha Mahjoub, Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers and Industrial Engineering 56 (2009) 1708–1712].     

Loading flexible manufacturing systems: a heuristic approach

In this study, heuristic algorithms are developed for loading Flexible Manufacturing Systems. The heuristic approach is an efficient way of planning the FMS with multiple nonlinear loading objectives.     

A holonic approach to dynamic manufacturing scheduling

Manufacturing scheduling is a complex combinatorial problem, particularly in distributed and dynamic environments. This paper presents a holonic approach to manufacturing scheduling, where the scheduling functions are distributed by several entities, combining their calculation power and local optimization capability. In this scheduling and control approach, the objective is to achieve fast and dynamic re-scheduling using a scheduling mechanism that evolves dynamically to combine centralized and distributed strategies, improving its responsiveness to emergence, instead of the complex and optimized scheduling algorithms found in traditional approaches.     

Complex scheduling of a printing process

The intricate nature of scheduling at a printing company is described. Many of its subtle operational complexities and sophisticated work order selection rules are explained in depth to emphasize the highly refined nature of a strongly sequence-dependent process. A simulation-based scheduling tool integrated with an enterprise resource planning (ERP) system is used to capture the required level of process detail. The results are comprehensive schedules that reflect the collective needs of the entire production process, improved understanding of interdepartmental effects, increased productivity, better visibility of future production requirements, and faster schedule turn around times.     

A cutting and scheduling problem in float glass manufacturing

This paper considers a cutting and scheduling problem of minimizing scrap motivated by float glass manufacturing and introduces the float glass scheduling problem. We relate it to classical problems in the scheduling literature such as no-wait hybrid flow shops and cyclic scheduling. We show that the problem is NP-hard, and identify when each of the problem’s components are polynomially solvable and when they induce hardness. In addition, we propose a simple heuristic algorithm, provide its worst-case performance bounds, and demonstrate that the bounds are tight. When the number of machines is two, the worst-case performance is 5/3.     

A new heuristic for scheduling the two-stage flowshop with additional resources

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machine at the second stage. At the first stage, jobs use some additional resources which are available in limited quantities at any time. The resource requirements are of 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which solve to optimality the resource constrained scheduling problem at the first stage of the flowshop, and at the same time, minimize the makespan in the flowshop by selecting appropriate jobs for simultaneous processing. Several rules of job selection are considered. The performance of the proposed heuristic algorithms is analyzed by comparing solutions with the lower bound on the optimal makespan. The extensive computational experiment shows that the proposed heuristic algorithms are able to produce near-optimal solutions in short computational time.     

A decision analysis based system for formulating manufacturing strategy

Although a substantial number of decision and management science models of production management decisions have been developed, these models have not generally addressed the strategic framework of manufacturing, considered as an integrated pattern of decisions. They have usually been concerned with only one aspect of manufacturing strategy such as capacity or technology choice and have framed that choice using a single dimension of value such as cost. This study develops a comprehensive decision analysis model base which can be implemented as a DSS, to gain insight about the broader manufacturing strategy set. Decision trees, influence diagrams, Monte Carlo risk analysis and multiple criteria utility functions can contribute to a better understanding of and to decision support for manufacturing strategy formulation.     

A model, a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation

China plans to launch four small optical satellites and four small SAR satellites to form a natural disaster monitoring constellation. Data can be obtained by the constellation in all weather conditions for disaster alert and environmental damage analysis. The scheduling problem for the constellation consists of selecting and timetabling the observation activities to acquire the requested images of the earth surface and scheduling the download activities to transmit the image files to a set of ground stations. The scheduling problem is required to be solved every day in a typical 1-day horizon and it must respect complex satellite operational constraints as well as request preferences, such as visibility time windows, transition time between consecutive observations or downloads, memory capacity, energy capacity, polygon target requests and priorities. The objective is to maximize the rewards of the images taken and transmitted. We present a nonlinear model of the scheduling problem, develop a priority-based heuristic with conflict-avoided, limited backtracking and download-as-needed features, which produces satisfactory feasible plans in a very short time. A decision support system based on the model and the heuristic is also provided. The system performance shows a significant improvement with respect to faster and better scheduling of an earth observing satellite constellation.     

Multi-cost job routing and scheduling in Grid networks

A key problem in Grid networks is how to efficiently manage the available infrastructure, in order to satisfy user requirements and maximize resource utilization. This is in large part influenced by the algorithms responsible for the routing of data and the scheduling of tasks. In this paper, we present several multi-cost algorithms for the joint scheduling of the communication and computation resources that will be used by a Grid task. We propose a multi-cost scheme of polynomial complexity that performs immediate reservations and selects the computation resource to execute the task and determines the path to route the input data. Furthermore, we introduce multi-cost algorithms that perform advance reservations and thus also find the starting times for the data transmission and the task execution. We initially present an optimal scheme of non-polynomial complexity and by appropriately pruning the set of candidate paths we also give a heuristic algorithm of polynomial complexity. Our performance results indicate that in a Grid network in which tasks are either CPU- or data-intensive (or both), it is beneficial for the scheduling algorithm to jointly consider the computational and communication problems. A comparison between immediate and advance reservation schemes shows the trade-offs with respect to task blocking probability, end-to-end delay and the complexity of the algorithms.     

Real-time feedback scheduling of flexible manufacturing systems

A genetic manufacturing environment is considered. The emphasis is on small-lot, discrete, and asynchronous type of manufacturing systems rather than high volume and continuous type. Two classes of scheduling policies are proposed to render the machine stable. The policies are of feedback type. The decision is made in real-time and on-line.     

An optimization-based decision support system for ship scheduling

The bulk carriers in the world merchant fleet typically operate full between a loading and discharging port, then run empty until they reach the next loading port. The shipping rates of bulk trades are set on supply/demand bases and fluctuate considerably. Thus the proper scheduling of ships in bulk trade has the great potential of improving the owner's profit and economic performance of shipping. This paper considers an optimization-based Decision Support System for ship scheduling. The typical optimization models for scheduling the ships are briefly reviewed and classified by the underlying idea. Then a prototype MoDiSS(Model-based SS in Ship Scheduling) which is based on a set-packing model has been developed on PC base with proper GUI. The performance of the system has been tested and examined using various ship scheduling scenarios and thereby the effectiveness of the system is validated satisfactorily.     

A decision support tool to facilitate the design of cellular manufacturing layouts

This paper presents a decision support tool that can be used by practitioners and industrialists to solve practical cell formation problems. The tool is based on a cell formation algorithm that employs a set of heuristic rules to obtain a quasi-optimal solution from both component routing information and other significant production data. The algorithm has been tested on a number of data sets obtained from the literature. The test results have demonstrated that in many cases the algorithm has produced an exceptional performance in terms of the grouping efficiency, grouping efficacy and quality index measures. The algorithm, to an extent, overcomes common problems in existing cell formation methods such as in dealing with ill-structured matrices and achieving rational cell sizes.     

A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction

Manufacturing scheduling strategies have historically emphasized cycle time; in almost all cases, energy and environmental factors have not been considered in scheduling. This paper presents a new mathematical programming model of the flow shop scheduling problem that considers peak power load, energy consumption, and associated carbon footprint in addition to cycle time. The new model is demonstrated using a simple case study: a flow shop where two machines are employed to produce a variety of parts. In addition to the processing order of the jobs, the proposed scheduling problem considers the operation speed as an independent variable, which can be changed to affect the peak load and energy consumption. Even with a single objective, finding an optimal schedule is notoriously difficult, so directly applying commercial software to this multi-objective scheduling problem requires significant computation time. This paper calls for the development of more specialized algorithms for this new scheduling problem and examines computationally tractable approaches for finding near-optimal schedules.