Lập kế hoạch sản xuất & dự án: Tuyển tập các bài viết tưởng niệm Salah Elmaghraby

• Tác giả: P. Simin Pulat
• Chuyên ngành: Nghiên cứu vận hành
• Đề tài: Essays in Production, Project Planning and Scheduling
• Loại tài liệu: Tuyển tập nghiên cứu
• Năm xuất bản: 2014
• Địa điểm: New York

Tóm tắt

I. Tổng quan về lập kế hoạch và lịch trình sản xuất dự án

Lập kế hoạch và lịch trình sản xuất dự án là lĩnh vực nghiên cứu cốt lõi trong nghiên cứu vận hành. Bộ sưu tập 'Essays in Production Project Planning and Scheduling' tập hợp các công trình học thuật nhằm tôn vinh giáo sư Salah Elmaghraby. Ông là người có đóng góp to lớn cho sự phát triển của nghiên cứu vận hành từ những ngày đầu thành lập. Elmaghraby nhận bằng tiến sĩ từ Đại học Cornell năm 1958. Ông đã dành cả sự nghiệp để xây dựng nền tảng lý thuyết cho việc lập lịch sản xuất. Các bài viết trong tuyển tập này bao gồm nhiều chủ đề then chốt. Đó là tối ưu hóa chuỗi cung ứng, quản lý tồn kho, lập lịch trình công việc và lập kế hoạch sản xuất đa kỳ. Phương pháp tiếp cận sử dụng cả mô hình toán học lẫn kỹ thuật mô phỏng. Mục tiêu chính là cân bằng giữa năng lực sản xuất và nhu cầu thị trường. Công trình của Elmaghraby tạo nền tảng cho nhiều thuật toán lập lịch hiện đại. Tuyển tập này phản ánh tầm ảnh hưởng sâu rộng của ông đối với cả lý thuyết và thực hành quản lý sản xuất công nghiệp.

1.1. Bối cảnh lịch sử và nguồn gốc học thuật

Nghiên cứu vận hành bắt đầu phát triển mạnh mẽ từ sau Thế chiến thứ hai. Giáo sư Salah Elmaghraby nằm trong thế hệ tiên phong đặt nền móng cho lĩnh vực này. Ông gia nhập Đại học Cornell và hoàn thành bằng tiến sĩ năm 1958. Từ đó, Elmaghraby liên tục có những đóng góp đột phá về lý thuyết lịch trình sản xuất. Các nghiên cứu của ông bao gồm kỹ thuật Mạng, lý thuyết đồ thị và quy hoạch động. Tuyển tập Essays in Production Project Planning and Scheduling được xuất bản bởi Springer năm 2014. Đây là cuốn Festschrift vinh danh sự nghiệp nghiên cứu kéo dài hơn năm thập kỷ của ông. Nhiều tác giả hàng đầu trong lĩnh vực nghiên cứu vận hành đã đóng góp bài viết cho tuyển tập này.

1.2. Phạm vi và cấu trúc nội dung tuyển tập

Tuyển tập thuộc Series Nghiên cứu Vận hành và Khoa học Quản lý của Springer, tập 200. Ba biên tập viên chính là P. Simin Pulat, Subhash C. Sarin và Reha Uzsoy. Nội dung trải rộng trên nhiều chủ đề từ lập kế hoạch sản xuất đến quản lý chuỗi cung ứng. Các bài viết sử dụng phương pháp quy hoạch tuyến tính, quy hoạch động và tối ưu tổ hợp. Một số chương tập trung vào mô hình chi phí sản xuất và hàm năng lực. Chương khác phân tích mối quan hệ giữa giá cả, sản lượng và thời gian giao hàng. Tuyển tập cũng đề cập đến ứng dụng hệ thống thông tin và công nghệ ontology trong quản lý sản xuất. Cấu trúc này phản ánh tính liên ngành của nghiên cứu lập kế hoạch sản xuất hiện đại.

II. Các vấn đề cốt lõi trong lập lịch trình sản xuất dự án

Lập lịch trình sản xuất dự án đối mặt với nhiều thách thức phức tạp. Bài toán cân bằng giữa nhu cầu thị trường và năng lực sản xuất luôn là vấn đề trung tâm. Hàm năng lực sản xuất, hay Capacity Function, giới hạn sản lượng tối đa trong mỗi kỳ. Mô hình của Karmarkar năm 1989 chỉ ra mối quan hệ phi tuyến giữa tồn kho công việc đang thực hiện và sản lượng. Điều này tạo ra độ phức tạp tính toán đáng kể cho bài toán lập lịch. Một vấn đề khác là quản lý thời gian giao hàng cho khách hàng. Little's Law liên hệ giữa lượng công việc tồn đọng và thời gian chờ đợi trung bình. Khách hàng thường đặt giới hạn về số đơn hàng được giao sớm. Yếu tố chi phí cũng tạo thêm áp lực, bao gồm chi phí lưu kho, chi phí sản xuất và chi phí thiếu hụt. Bài toán đa mục tiêu này đòi hỏi phương pháp tối ưu hóa toàn diện. Các ràng buộc về tồn kho thành phẩm và công việc đang thực hiện càng làm tăng độ phức tạp của bài toán lập kế hoạch sản xuất.

2.1. Hàm năng lực sản xuất và giới hạn tài nguyên

Hàm năng lực sản xuất đóng vai trò quyết định trong mô hình lập kế hoạch. Công thức của Karmarkar mô tả mối quan hệ giữa mức tồn kho công việc đang thực hiện và sản lượng tối đa. Sản lượng trong mỗi kỳ bị ràng buộc bởi hàm năng lực tương ứng. Khi lượng đơn hàng tồn đọng tăng, thời gian chờ đợi trung bình cũng tăng theo. Điều này ảnh hưởng trực tiếp đến khả năng đáp ứng nhu cầu thị trường. Mô hình tính đến chi phí vận hành biến đổi, chi phí lưu kho và chi phí nhân công. Việc xác định chính xác hàm năng lực là bước quan trọng để xây dựng kế hoạch sản xuất khả thi. Các nhà nghiên cứu đã phát triển nhiều kỹ thuật để ước lượng tham số của hàm này từ dữ liệu thực tế.

2.2. Cân bằng giữa giá cả sản lượng và thời gian giao hàng

Mối quan hệ giữa giá cả và nhu cầu là yếu tố then chốt trong lập kế hoạch sản xuất. Hàm nhu cầu được biểu diễn dưới dạng tuyến tính, phụ thuộc vào giá bán và thời gian giao hàng. Khi giá tăng, nhu cầu giảm. Khi thời gian giao hàng dài hơn, khách hàng có thể tìm nhà cung cấp khác. Little's Law cung cấp mối liên hệ toán học giữa tồn kho công việc và thời gian chờ đợi. Bài toán tối ưu hóa phải cân nhắc đồng thời doanh thu, chi phí sản xuất và chi phí lưu kho. Mô hình CF kết hợp các yếu tố này thành bài toán quy hoạch tuyến tính nhiều kỳ. Mục tiêu là tối đa hóa tổng lợi nhuận biên trong toàn bộ chu kỳ lập kế hoạch. Việc giao hàng sớm có thể tăng sự hài lòng nhưng lại làm tăng chi phí tồn kho thành phẩm.

III. Phương pháp và mô hình tối ưu hóa trong lập kế hoạch sản xuất

Nhiều phương pháp tối ưu hóa đã được phát triển để giải quyết bài toán lập kế hoạch sản xuất. Mô hình CF dựa trên hàm năng lực là một trong những cách tiếp cận hiệu quả nhất. Bài toán được xây dựng dưới dạng quy hoạch tuyến tính với các ràng buộc cân bằng. Ràng buộc cân bằng công việc đang thực hiện đảm bảo tính liên tục giữa các kỳ sản xuất. Ràng buộc cân bằng tồn kho thành phẩm kiểm soát dòng chảy sản phẩm từ sản xuất đến bán hàng. Hàm mục tiêu tối đa hóa tổng doanh thu trừ đi toàn bộ chi phí biến đổi. Các kỹ thuật quy hoạch động cũng được áp dụng để xử lý bài toán nhiều giai đoạn. Phương pháp ontology và ngôn ngữ đặc thù miền hỗ trợ quản lý tri thức sản xuất. Công cụ tính toán hiện đại cho phép xây dựng cơ sở tri thức có thể đọc được bằng máy. UML được sử dụng để thiết kế mô hình hướng đối tượng cho hệ thống sản xuất. Sự kết hợp giữa lý thuyết và công nghệ tạo ra giải pháp toàn diện cho ngành công nghiệp sản xuất.

3.1. Mô hình CF và công thức tối ưu hóa đa kỳ

Mô hình CF sử dụng hàm năng lực để ràng buộc sản lượng tối đa mỗi kỳ. Hàm này biểu diễn mối quan hệ giữa mức tồn kho công việc và sản lượng khả thi. Bài toán tối đa hóa tổng lợi nhuận biên bao gồm doanh thu bán hàng và các khoản chi phí. Chi phí bao gồm chi phí vận hành biến đổi, chi phí lưu kho và chi phí nhân công. Các ràng buộc cân bằng đảm bảo tính nhất quán của dòng vật liệu qua các kỳ. Biến quyết định bao gồm giá bán, sản lượng, tồn kho và lượng đặt hàng bổ sung. Bài toán cũng tính đến thời gian giao hàng dự kiến cho từng kỳ. Ràng buộc giao hàng cho phép giao sớm hơn thời hạn nhưng có giới hạn số lượng. Mô hình này cung cấp khung phân tích toàn diện cho nhà quản lý sản xuất.

3.2. Ứng dụng ontology và công nghệ thông tin trong quản lý sản xuất

Ontology là công cụ mạnh mẽ để đạt khả năng tương tác giữa các hệ thống thông tin. Vernadet năm 2007 đề xuất xây dựng ontology sử dụng kho siêu dữ liệu. Trong lĩnh vực tính toán, ontology định nghĩa chính thức các lớp khái niệm trong một miền cụ thể. Các thuộc tính của lớp biểu diễn đặc trưng và tính năng của khái niệm đó. Ontology cùng với các thể hiện tạo thành cơ sở tri thức có thể đọc bằng máy. Công cụ tính toán hỗ trợ soạn thảo, chỉnh sửa và trực quan hóa ontology. Ngôn ngữ đặc thù miền DSL được phát triển để dễ sử dụng hơn cho chuyên gia lĩnh vực. UML cung cấp mười ba loại sơ đồ để mô hình hóa kiến trúc và cấu trúc ứng dụng. Chiến lược này giúp thu hẹp khoảng cách giữa chuyên gia công nghệ và chuyên gia sản xuất.

IV. Kết luận và ứng dụng thực tiễn của lập kế hoạch sản xuất dự án

Tuyển tập Essays in Production Project Planning and Scheduling để lại di sản học thuật quý giá. Công trình của giáo sư Elmaghraby tạo nền tảng vững chắc cho nhiều thế hệ nhà nghiên cứu. Các mô hình tối ưu hóa được trình bày có khả năng ứng dụng rộng rãi trong thực tế. Ngành sản xuất chế tạo sử dụng các phương pháp này để tối ưu hóa lịch trình và giảm chi phí. Chuỗi cung ứng hiện đại áp dụng kỹ thuật lập kế hoạch đa kỳ để cân bằng cung cầu. Công nghệ ontology hỗ trợ tích hợp hệ thống thông tin trong môi trường sản xuất thông minh. Các hàm năng lực sản xuất giúp doanh nghiệp dự báo năng lực và ra quyết định đầu tư. Phương pháp quy hoạch động xử lý hiệu quả bài toán có nhiều giai đoạn liên kết. Tương lai của lĩnh vực này hướng đến tích hợp trí tuệ nhân tạo và học máy. Các nguyên tắc cơ bản do Elmaghraby và cộng sự đề xuất vẫn giữ nguyên giá trị. Sự kết hợp giữa lý thuyết toán học và công nghệ số sẽ định hình ngành quản lý sản xuất.

4.1. Ứng dụng trong quản lý chuỗi cung ứng hiện đại

Nguyên tắc lập kế hoạch sản xuất được áp dụng rộng rãi trong quản lý chuỗi cung ứng. Doanh nghiệp sử dụng mô hình cân bằng để tối ưu hóa tồn kho toàn chuỗi. Kỹ thuật lập lịch đa kỳ giúp điều phối sản lượng giữa nhiều nhà máy và kho hàng. Hàm năng lực sản xuất hỗ trợ đánh giá năng lực cung ứng thực tế. Phương pháp ontology cho phép chia sẻ dữ liệu giữa các đối tác trong chuỗi cung ứng. Hệ thống thông tin tích hợp giảm thời gian ra quyết định và tăng độ chính xác. Các công ty sản xuất lớn đã áp dụng thành công nhiều kỹ thuật từ tuyển tập này. Kết quả bao gồm giảm thời gian giao hàng, giảm chi phí tồn kho và tăng mức độ hài lòng của khách hàng.

4.2. Hướng phát triển tương lai của lĩnh vực lập kế hoạch sản xuất

Lĩnh vực lập kế hoạch sản xuất đang chuyển đổi mạnh mẽ nhờ công nghệ mới. Trí tuệ nhân tạo và học máy hỗ trợ dự báo nhu cầu chính xác hơn. Internet vạn vật cung cấp dữ liệu thời gian thực về tình trạng sản xuất. Kỹ thuật tối ưu hóa dựa trên dữ liệu lớn cho phép xử lý bài toán quy mô lớn. Ngôn ngữ đặc thù miền giúp chuyên gia sản xuất xây dựng mô hình mà không cần kiến thức lập trình sâu. Tích hợp ontology với công nghệ ngữ nghĩa web mở ra khả năng tự động hóa quy trình. Các nguyên tắc nền tảng do Elmaghraby đề xuất tiếp tục là kim chỉ nam cho nghiên cứu mới. Sự hội tụ giữa lý thuyết toán học cổ điển và công nghệ số tạo ra cơ hội đột phá cho ngành sản xuất thông minh.

Trích đoạn nội dung tài liệu

International Series in Operations Research & Management Science Volume: 200 Series Editor Frederick S. Hillier Stanford University, CA, USA For further volumes: http://www. Simin Pulat • Subhash C. Sarin • Reha Uzsoy Editors Essays in Production, Project Planning and Scheduling A Festschrift in Honor of Salah Elmaghraby 2123 Editors P. Simin Pulat Reha Uzsoy College of Engineering Dept of Industrial & Systems Engineering The University of Oklahoma North Carolina State University Norman Raleigh Oklahoma North Carolina USA USA Subhash C. Sarin Dept of Industrial & Systems Engineering Virginia Tech Blacksburg Virginia USA ISSN 0884-8289 ISSN 2214-7934 (electronic) ISBN 978-1-4614-9055-5 ISBN 978-1-4614-9056-2 (eBook) DOI 10.1007/978-1-4614-9056-2 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2013954994 © Springer Science+Business Media New York 2014 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright Law. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.com) Preface This festschrift is devoted to recognize the career of a man who not only witnessed the growth of operations research from its inception, but also contributed significantly to this growth. Elmaghraby received his doctorate degree from Cornell University in 1958, and since then, his scholarly contributions have enriched the fields of production planning and scheduling and project scheduling. This collection of papers is contributed in his honor by his students, colleagues, and acquaintances. It offers a tribute to the inspiration received from his work, and from his guidance and advice over the years, and recognizes the legacy of his many contributions. Elmaghraby is a pioneer in the area of project scheduling (in particular, project planning and control through network models, for which he coined the term ‘ac- tivity networks’). In his initial work in this area, he developed an algebra based on signal flow graphs and semi-Markov processes for analyzing generalized ac- tivity networks involving activities with probabilistic durations. This work led to the development of what was later known as the Graphical Evaluation and Review Technique (GERT), and GERT simulation models. He has made fundamental contri- butions in determining criticality indices for activities, in developing methodologies for project compression and time/cost analysis, and in the use of stochastic and chance-constrained programming and Petri Nets for the analysis of activity net- works. These contributions have been brought together in a seminal book in this area entitled, “Activity Networks: Project Planning and Control by Network Models” published by John Wiley, and a monograph on “Some Network Models in Manage- ment Science” published by Springer-Verlag. Elmaghraby also wrote one of the first books on production planning entitled, “The Design of Production Systems.” His fundamental contributions to the economic lot scheduling problem (ELSP) and economic manufacturing quantity (EMQ) analysis are also widely cited. This work presented a novel methodology using a combination of a dynamic programming-based model, integer programming, and a method to circumvent in- feasibility. He later extended this work to include learning and forgetting effects, and to the computation of power-of-two policies. Elmaghraby’s extensive work on a wide range of deterministic and stochastic sequencing and scheduling problems, arising in different machine environments, has resulted in many landmark contribu- tions which have advanced this field of study and have strengthened its knowledge v vi Preface base. It has offered novel ideas and effective methodologies relying on mathematical rigor for the solution of these problems. Elmaghraby is one of the rare individuals who have excelled both as a re- searcher and an administrator. He was appointed as University Professor and Director of the Graduate Program of Operations Research at North Carolina State University in his early 40’s, and over the years, he directed that program with aplomb without losing any of his scholarly productivity. That program flourished for all these years under his leadership, providing a world-class education to its students. His superb guidance and leadership by example in bringing quality in everything that he does has been a defining force that has shaped the careers of his students. It is, therefore, not surprising that, among his numerous awards, Dr. Elmaghraby has been recognized with the Frank and Lillian Gilbreth Award, the highest and most esteemed honor bestowed by The Institute of Industrial Engineers on individuals who have distin- guished themselves through contributions to the welfare of mankind in the field of industrial engineering. This volume brings together 14 contributions, which can be viewed under the following three main themes: operations research and its application in production planning, project scheduling, and production scheduling, inspired by, and in many cases based on, Dr. Elmaghraby’s work in these areas. The first five chapters are devoted to the first theme, followed by four chapters each devoted to the other two, respectively. An additional chapter is devoted to the vulnerability of multimodal freight systems. In the first chapter, “Ubiquitous OR in Production Systems”, Leon McGinnis puts forth an argument for a paradigm shift in OR education, from the traditional emphasis on teaching of standalone ‘artisan’ type tools (where each model is developed to address a specific problem), to a reusable platform that enables their broader and deeper penetration in a domain. This argument is made in view of the advent of new computer technologies, and for applications to production systems that are well understood. In the second chapter entitled “Integrated Production Planning and Pricing De- cisions in Congestion-Prone Capacitated Production Systems,” Upasani and Uzsoy address a production planning problem when the customer demand is sensitive to delivery lead times. Since the lead times are known to increase nonlinearly with the utilization of capacitated resources, a large reduction in price may increase demand to the extent that it can no longer be satisfied in a timely manner by available capacity, thereby negatively impacting customer satisfaction and future sales. They present an integrated model for dynamic pricing and production planning for a single product under workload-dependent lead times, and study interactions among pricing, sales, and lead times. Their investigation reveals a different behavior of the integrated model from a conventional model that ignores the congestive effect on resources because of price variations. A “Refined EM Method for Solving Linearly Constrained Optimization Prob- lems” is presented by Yu and Fang in the third chapter. They extend the original Electromagnetism-like Mechanism (EM) that has been widely used for solving global Preface vii optimization problems with box-constrained variables to solving optimization prob- lems with linear constraints, and call it a ‘Refined EM Method.’ The EM method is a stochastic search method that uses a functional evaluation at each step, and does not require any special information or structure about the objective function. The pro- posed method explicitly considers linear constraints in an efficient manner to direct sample points to attractive regions of the feasible domain. Results of a computational investigation are also presented that show the proposed method to outperform known methods and to converge rapidly to global optimal solutions. In “The Price of Anarchy for a Network of Queues in Heavy Traffic,” Shaler Stidham investigates the price of anarchy in a congestive network of facilities in which the cost functions at the facilities follow the characteristics of the waiting- time function for a queue with infinite waiting room. Similar to a network of parallel M/M/1 queues, Stidham develops an analytical expression for the price of anarchy for the GI/GI/1 network. In the fifth chapter entitled, “A Comparative Study of Procedures for the Multi- nomial Selection Problem,” Tollefson, Goldsman, Kleywegt, and Tovey address the multinomial selection problem originally formulated by Bechhofer, Elmaghraby, and Morse (1959), that of determining the number of trials needed to select the best among a given number of alternatives. The aim is to minimize the expected number of trials required while exceeding a lower bound on the probability of making the correct selection. The authors present a comparative study on the performances of various methods that have been proposed for this problem over the years. The sixth chapter is entitled, “Vulnerability of Multimodal Freight Systems.” In this chapter, Aydin and Pulat explore the vulnerability of multimodal freight transportation infrastructure in the face of extreme disruptive events. The freight transportation system constitutes a backbone of global economy. This study, mo- tivated by recent hurricane-related events encountered in the USA, examines the concepts of vulnerability, reliability, resilience, and risk, and the relationship among them, for the freight transportation infrastructure, and provides valuable insights on how vulnerable and resilient the transportation infrastructure is to extreme disruptive events. The following two chapters address stochastic project scheduling problems. In, “Scheduling and Financial Planning in Stochastic Activity Networks,” Dodin and Elimam analyze the impact of stochastic variations in the renewable and nonrenew- able resources required by each activity of the project, on project cost and duration. An analytical approach is used to determine the probability density functions of the project cost and duration. A linear programming model is used to distribute the re- sulting project budget over its activities and to minimize the project duration. Willy Herroelen presents “A Risk Integrated Methodology for Project Planning Under Un- certainty” in the eight chapter. A two-phase methodology is presented in the face of the risk of resource breakdown and variability of activity durations. In the first phase, the number of regular renewable resources to be allocated to the project is de- termined, and in phase two, first a resource-feasible proactive schedule is constructed, after which resource and time buffers are inserted to protect it against disruptions. viii Preface The schedule is then tested by simulating stochastic disruptions and by appropri- ately repairing it if it becomes infeasible. This approach provides an implementable schedule along with a workable reactive schedule procedure that can be invoked in case it becomes infeasible despite the protection built in it. In the ninth chapter, entitled, “Dynamic Resource Constrained Multi-Project Scheduling Problem with Earliness/Tardiness Costs,” Pamay, Bulbul, and Ulusoy address the problem of scheduling a new arriving project against a set of known re- newable resources when a number of projects are already in process. The due dates and earliness/tardiness penalties of the activities of the existing project are known while the due date of the new project is to be determined, which is accounted for by assigning a penalty cost per unit time the new project spends in the system. A heuristic method is proposed to solve large-sized problems, and its efficacy is demonstrated. “A Multi-Mode Resource-Constrained Project Scheduling Problem Including Multi-Skill Labor” is discussed by Santos and Tereso in the tenth chapter.